Q.). Give the derivations of decision tree.
Ans: Grammar can be represented using trees. Such trees representing derivations are called derivation
trees.
A derivation tree (also called a parse tree) for a G=( V_{N} Σ, P,S) is a tree satisfying the following:
1) Every vertex has a label which is a variable or terminal or A.
2) The root has label S.
3) The label of an internal vertex is a variable.
Ques 2)What are the closure properties of regular
sets?.
Note: Vertices 4-6 are sons of 3 written from the left, and S -> aAS is in P. Vertices 7 and 8 are sons of 5
written from the left, and A→ ba is a production in P. Vertex 5 is an internal vertex and its label is A,
which is a variable.
In figure 2.3, e.g., the sons of the root are 2 and 3 ordered from the left. So, the son of 2, viz. 10, is to the
left of any son of 3. The sons of 3 ordered from the left are 4-5-6. The vertices at level 2 in the left-to-
right ordering are 10-4-5-6. 4 is to the left of 5.
The sons of 5 ordered from the left are 7-8. So 4 is to the left of 7. Similarly, 8 is to the left of 9Thus the
order of the leaves from the left is 10-4-7-8-9.
Que .) Show that every regular language is context- free language.
Ans: From recursive definition of Regular set we know ♀️ and are regular expression. If R is regular
expression, then R+R (Union), R.R (Concatenation) and R (Kleene Star) are also regular expressions. A
regular expression R is a string of terminal symbols. The o and e are also CFL and we know CFL are closed
under Union, concatenation and Kleene star. Therefore, every regular language is a CFL.
Ques .) Consider the CFG G defined by productions: S-> aS|Sb|a|b. Construct the language L. (G) that
does not have “ba” as a substring.
↙️↙️ (1) Ans: Let n be the length of the string w.
1) Base case: n = 1. Since S→ a and S→ b, “a” and “b” are in the language. Neither of these contains “ba”.
2) Inductive Hypothesis: All strings in L(G) with length n 1 do not contain “ba”.
3) Inductive Step: Let w be a string of length n. There Are two recursive productions, and thus two cases:
i) SaS. Therefore w = aw, where lw’l=n – 1, so w’ does not contain “ba”. The only way for w to
contain “ba” is if the new character – the “a” at the beginning is a part of it. The new
↘️↘️ (2)
character – cannot be the “b”, as it is an “a”, and it cannot be the “a”, as it is the first
character. Therefore, if w= aw’, w does not contain “ba”.
ii) S-Sb. Therefore w=w’b, where lw’l=n-1, so w’ does not contain “ba”. The only way for w to
contain “ba” is if the new character- the “b” at the end – is a part of it. The new character
cannot be the “a”, as it is a “b”, and it cannot be the “b”. as it is the last character. Therefore,
if w = w’b, w does not contain “ba”.
Therefore, the inductive hypothesis also holds for n, and therefore for all strings. Therefore, no strings in
G contain “ba”
