DPDA and Context Free Languages Multiple Choice Questions with Answers

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “DPDA and Context Free Languages”.

1. Context free grammar is called Type 2 grammar because of ______________ hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
View Answer

Answer: c
Explanation: Chomsky hierarchy decide four type of language :Type 3- Regular Language, Type 2-Context free language, Type 1-Context Sensitive Language, Type 0- Unrestricted or Recursively Ennumerable language.

2. a→b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language
View Answer

Answer: b
Explanation: A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and non terminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are some languages that cannot be described by context-free grammars, but can be described by CSG.

3. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
View Answer

Answer: a
Explanation: V is the set of non terminal symbols while T is the st of terminal symbols, their intersection would always be null.

4. If P is the production, for the given statement, state true or false.
P: V->(V∑T)* represents that the left hand side production rule has no right or left context.
a) true
b) false
View Answer

Answer: a
Explanation: Here the production P is from the definition of Context free grammar and thus, has no right or left context.

5. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
View Answer

Answer: b
Explanation: The grammar with right recursive production is known as Right recursive grammar. Right recursive production is of the form X->aX where a is a terminal and X is a non terminal.

6. If the partial derivation tree contains the root as the starting variable, the form is known as:
a) Chomsky hierarchy
b) Sentential form
c) Root form
d) None of the mentioned
View Answer

Answer: b
Explanation: Example: For any grammar, productions be:
S->AB
A->aaA| ^
B->Bb| ^
The partial derivation tree can be drawn as:

Since it has the root as S, this can be said to be in sentential form.

7. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting wth an a and ending with a b, with something in the middle.
a) a(a*Ub*)b
b) a*(aUb)b*
c) a(a*b*)b
d) None of the mentioned
View Answer

Answer: a
Explanation: The grammar for the same language can be stated as :
(1) S → aMb
(2) M → A
(3) M → B
(4) A → e
(5) A → aA
(6) B → e
(7) B → bB

8. Which of the following is the correct representation of grammar for the given regular expression?
a(aUb)*b

a) (1) S → aMb
(2) M → e
(3) M → aM
(4) M → bM

b) (1) S → aMb
(2) M → Mab
(3) M → aM
(4) M → bM

c) (1) S → aMb
(2) M → e
(3) M → aMb
(4) M → bMa

d) None of the mentioned
View Answer

Answer: a
Explanation:
The basic idea of grammar formalisms is to capture the structure of string by
a) using special symbols to stand for substrings of a particular structure
b) using rules to specify how the substrings are combined to form new substrings.

9. A CFG consist of the following elements:
a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
View Answer

Answer: d
Explanation: A CFG consists of:
a) a set of terminals, which are characters of alphabets that appear in the string generated by the grammar.
b) a set of non terminals, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols.
c) a set of productions, which are set of rules to transit from one state to other forming up the string
d) a start symbol, a special non terminal symbol that appears in the initial string generated in the grammar.

10. A CFG for a program describing strings of letters with the word “main” somewhere in the string:
a) -> m a i n
-> | epsilon
-> A | B | … | Z | a | b … | z

b) –> m a i n
–>
–> A | B | … | Z | a | b … | z

c) –> m a i n
–> | epsilon
–> A | B | … | Z | a | b … | z

d) None of the mentioned
View Answer

Answer: a
Explanation: None.