Theory of Computation

“Sentential Forms”.

1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
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



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