MCQs on Context free Grammar and Context Sensitive Languages in Theory of Automata
The entity which generate Language is termed as:
(a) Automata
(b) Tokens
(c) Strings
(d) Grammar
The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
(a) 5
(b) 7
(c) 3
(d) 8
Which of the following statement is correct?
(a) All context free grammar are regular grammar but not vice versa
(b) All Regular grammar are context free but not vice versa
(c) Regular grammar and context free grammar are the same entity
(d) None of the mentioned
Context sensitive grammar (CSL) is also called?
(a) Length increasing grammar
(b) Non contracting Grammar
(c) Type 1 Grammar
(d) All of these
| GRAMMAR | AUTOMATA MACHINE | TYPE |
| Regular | Finite State Automaton | Type 3: Regular |
| Context Free | Pushdown Automaton | Type 2: Context Free |
| Context Sensitive | Linear Bounded Automaton | Type 1: CS |
| Recursively Enumerable | Turing Machine | Type 0: Unrestricted |
Which of the following is Type 3 language or Type 3 grammar?
(a) Regular grammar/ Regular language
(b) Context Free Grammar / Context Free
language
(c) Context Sensitive Grammar / Context Sensitive language
(d) Recursively Enumerable
Which of the following is Type 2 language or Type 2 grammar?
(a) Regular grammar/ Regular language
(b) Context Free Grammar / Context Free
language
(c) Context Sensitive Grammar / Context Sensitive language
(d) Recursively Enumerable
Which of the following is Type 1 language or Type 1 grammar?
(a) Regular grammar/ Regular language
(b) Context Free Grammar / Context Free
language
(c) Context Sensitive Grammar / Context Sensitive language
(d) Recursively Enumerable
Which of the following is Type 0 language?
(a) Regular grammar/ Regular language
(b) Context Free Grammar / Context Free
language
(c) Context Sensitive Grammar / Context Sensitive language
(d) Recursively Enumerable
Which of the following Machine is specific for Regular grammar?
(a) Finite state automata
(b) Push down automata
(c) Linear bounded automata
(d) Turing Machine with deterministic logic, unbounded infinite length of tape.
Which of the following Machine is specific for Context free grammar?
(a) Finite state automata
(b) Push down automata
(c) Linear bounded automata
(d) Turing Machine
Which of the following Machine is specific for Context sensitive grammar?
(a) Finite state automata
(b) Push down automata
(c) Linear bounded automata
(d) Turing Machine
Explanation: Linear Bounded Automaton is a
1.Turing Machine with Multi-track
2.Turing Machine with a bounded finite length of the tape.
3.Turing Machine with Non-deterministic logic
Which of the following Machine is specific for Recursively enumerable languages?
(a) Finite state automata
(b) Push down automata
(c) Linear bounded automata
(d) Turing Machine
A context free language is called ambiguous if there exists a string that can have?
(a) only one parse tree
(b) more than one parse tree
(c) no parse tree
(d) Partial parse tree
Explanation:
For example, we
have a CFG.
S →XY | mmY
X →m | Xm
Y →n
The context free grammar
X → XX | aXb | bXa | ɛ
generates __?
(a) Number of a’s followed by any number of b’s
(b) Unequal number of a’s and b’s
(c) Equal number of a’s and b’s
(d) None of these
Production Rule:
aYb->agb
belongs to which of the following languages?
(a) Recursively Enumerable Language
(b) Context free Language
(c) Context Sensitive Language
(d) Regular Language
Which of the following language cannot be accepted by a regular expression?
(a) Language of a set of numbers divisible by 4
(b) Language of a set of binary complement
(c) Language of a set of 0n1n
(d) Language of a set of string with odd number of 0
The minimum number of productions required to produce a language consisting of palindromes as a strings defined over ∑={0,1} is
(a) 4
(b) 5
(c) 6
(d) 7
Which of the following statement is true about regular grammar?
(a) Regular grammar and context free
(b) All context free grammar are regular grammar but not vice versa
(c) All Regular grammar are context free but not vice versa grammar are the same entity
(d) All of these
Are ambiguous grammar context free?
(a) Yes
(b) No
