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
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.
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
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
Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.
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
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
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
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
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
Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.
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
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
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S
10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
View Answer
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.
- Buy Computer Science Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Buy Automata Theory Books
- Apply for Automata Theory Internship
