Automata Theory Questions and Answers – Context Free Grammar-Derivations and Definitions

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Context Free Grammar-Derivations and Definitions”.

1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
View Answer

Answer: c
Explanation: The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
View Answer

Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.

3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
View Answer

Answer: d
Explanation: Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.
Regular language by context free grammar
advertisement
advertisement

4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
View Answer

Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.

5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
View Answer

Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
View Answer

Answer: c
Explanation: According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.

7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
View Answer

Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.
advertisement

8. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
View Answer

Answer: c
Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}

9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
View Answer

Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
advertisement

10. Are ambiguous grammar context free?
a) Yes
b) No
View Answer

Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.