Automata Theory Questions and Answers – Sentential Forms

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Sentential Forms”.

1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
View Answer

Answer: a
Explanation: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
advertisement

2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
View Answer

Answer: c
Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
View Answer

Answer: d
Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: c
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01

5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: b
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
advertisement

6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
View Answer

Answer: b
Explanation: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.

7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned
d) None of the mentioned
View Answer

Answer: c
Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.
advertisement

8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
View Answer

Answer: a
Explanation: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.

9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned
View Answer

Answer: c
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
advertisement

10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
View Answer

Answer: a
Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.

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.

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 & technical discussions at Telegram SanfoundryClasses.