“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.
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
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
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.
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
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
