Author: Vivek Kulkarni - It-rockers

Theory of ComputationSolutions for review questionsAuthor: Vivek Kulkarni( vivek kulkarni@yahoo.com )Chapter-5: GrammarsSolutions for Review Questions@ Oxford University Press 2013. All rights reserved.1

Theory of ComputationQ.1Solutions for review questionsWrite a context-free grammar (CFG) which generates the language L denoted by:(a b)* bbb (a b) *Solution:The CFG required is,S a A b A bbbQ.2Distinguish between the type-0 and type-1 grammars.Solution:Refer to the sections 5.11.1 and 5.11.2.Q.3Explain Greibach normal form with the help of an example.Solution:Refer to the sections 5.10.2.Q.4Consider the grammar G {(S, A), (0, 1), P, S}, where P consists of:S 0AS 0A S1A SS 10Show the leftmost derivation and rightmost derivation for the input string ‘001100’.Solution:Leftmost Derivation:S 0ASS 0 S 1A SS 0 0 1A SS 00110SS 001100@ Oxford University Press 2013. All rights reserved.2

Theory of ComputationSolutions for review questionsRightmost Derivation:S 0ASS 0A0S 0S1A0S 0S1100S 001100Q.5What is a derivation tree? Give suitable examples.Solution:Refer to the section 5.6.Q.6Convert the following grammar to CNF:S ABAA aA B bB Solution:Refer to the example 5.42 from the book.Q.7Find the CFL associated with the following CFG:S aB bAA a aS bAAB b bS aBBSolution:Refer to the example 5.6 from the book.Q.8Is the following grammar ambiguous?S 0A1 0BAA S01 0B 1B 1@ Oxford University Press 2013. All rights reserved.3

Theory of ComputationSolutions for review questionsSolution:The grammar is unambiguous, as for any string there is only one way of derivation possible.Q.9Show that the following CFG is ambiguous. Remove the ambiguity and write an equivalentunambiguous CFG.S S S S*S 4Solution:The grammar is ambiguous. We can show two different ways to derive the string ‘4 4 * 4’. Below arethe two different leftmost derivations for the same string,1.S S SS 4 SS 4 S*SS 4 4*SS 4 4*42.S S*SS S S*SS 4 S*SS 4 4*SS 4 4*4The equivalent CFG after removing the ambiguity is,S S T TT T*U UU 4Q.10Define the following and give appropriate examples:(a)Derivation graph(b)Unrestricted grammar(c)CFG@ Oxford University Press 2013. All rights reserved.4

Theory of ComputationSolutions for review questionsSolution:(a)Derivation graph: Refer to the section 5.17.(b)Unrestricted grammar: Refer to the section 5.11.1.(c)CFG: Refer to the section 5.11.3.Q.11What is regular grammar? State its category in Chomsky hierarchy.Solution:: Refer to the section 5.11.4.Q.12Write a CFG, which accepts the language L, where:L {0i 1j 0k j i k}.Using this grammar, show the derivation of the string ‘0111100’.Solution:The CFG can be written as,S ACBA 0A1 B 1B0 C 1C 1We can see that A generates equal number of 0’s and 1’s. The symbol B adds equal number of 1’s as itadds the number of 0’s. If we consider the sequence AB, then it generates number of 1’s, j i k. Thesymbol C is introduced will generate one or more 1’s to achieve j i k.Let us derive the string ‘0111100’ using the above CFG.S ACB 0A1CB 01CB 011B 0111B0 01111B00 0111100(using A )(using B )@ Oxford University Press 2013. All rights reserved.5

Theory of ComputationQ.13Solutions for review questionsConvert the following right-linear grammar to its equivalent left-linear grammar:S aA bB aS aA bA B aB Solution:As there is a self-loop on the start symbol ‘S a S’, let us introduce a new start symbol T. The modifiedCFG is,T SS aA bB aS aA bA B aB Let us draw the FA corresponding to the given right-liner grammar. The positions of the start and thefinal states need to be exchanged followed by the reversal of all the transitions. We get the reversed FA asshown in the figure below.From the reversed FA we can write the equivalent left-linear grammar as below,T Sa B AS Sa A Ab SaB Ba BbQ.14Write the CFG for each of the following languages:(1)The set of palindromes over alphabet {a, b}@ Oxford University Press 2013. All rights reserved.6

Theory of ComputationSolutions for review questions(2)The set of all strings over alphabet {a, b} with exactly twice many a’s as b’s(3)L {ai bj ck i j or j k}Solution:(1) S a S a b S b a b (2) Refer to the example 5.25 from the book.(3) i j means, either i j or, i j. Same holds true for j k.For the condition i j we can write the CFG as,X SCS aSb A BA aA B bB C cC Similarly for the condition j k we can add the following productions,X ATT bTc B CTherefore, the resultant grammar is,X SC ATS aSb A BT bTc B CA aA B bB C cC Q.15Consider the following languages:L1 {an b2n cm n, m 0}L2 {an bm c2m n, m 0}Write the CFG for each of them.@ Oxford University Press 2013. All rights reserved.7

Theory of ComputationSolutions for review questionsSolution:The CFG for the L1 is,X SCS aSbb C cC The CFG for the L2 is,X ATT bTcc A aA Q.16Write a short note on the applications of CFG.Solution:Refer to the section 5.18.Q.17Write a context-free grammar (CFG), which defines a language L over {a, b} such that Lcontains the words in which, the letter b does not appear consecutively three times.Solution:The regular expression for such a language can be written as,(a* b a* b a )*It can be written as CFG as shown below,S XS X AbAbBA aA B aA aQ.18Remove the unit productions from the following CFG.S aX YbX SY bY b@ Oxford University Press 2013. All rights reserved.8

Theory of ComputationSolutions for review questionsSolution:Substituting for X in S we get,S aS YbY bY bQ.19Consider grammar G defined using the productions:E E E E * E (E) idIs the grammar G ambiguous? Justify your answer.Solution:Refer to the section 5.8.Q.20Write a CFG that will generate the language:L {WCWR W (a, b)*, and WR is the reverse of W}Using this grammar, show the leftmost derivation, rightmost derivation, and derivation tree forthe input string ‘ababCbaba’.Solution:The CFG can be written as,S aSa bSb CThis is nothing but a CFG for all the palindrome strings with middle symbol as ‘C’.Leftmost derivation for ‘ababCbaba’:S aSa abSba abaSaba ababSbaba ababCbabaAs S is the only non-terminal on the right hand side of any production, even the rightmost derivationlooks exactly same.The derivation tree is as shown below,@ Oxford University Press 2013. All rights reserved.9

Theory of ComputationQ.21Solutions for review questionsWrite the CFGs generating the following languages, for n 0:(1)(bdb)nCn(2)(ab)n (cd)nSolution:(1)S bdbSC bdbC(2)S abScd abcdQ.22Find the CFG without -productions equivalent to the following grammar. Assume S is the startsymbol.S ABaCA BCB b C D D CSolution:Here, C, B, D and A are the nullable non-terminals.Hence, the CFG without -productions equivalent to the above grammar can be written as,@ Oxford University Press 2013. All rights reserved.10

Theory of ComputationSolutions for review questionsS ABaC ABa AaC BaC Aa Ba aC aA BC B CB bC DD CQ.23Is the language L {an bm n m} context-free? If yes, write the CFG defining this language.Solution:S aSb aA bBA aA B bB As n m, n can either be greater than m or less than m.‘S a S b’ always generates equal number of a’s and b’s. Once that is done, the middle S can either bederived as ‘S a A’ or ‘S b B’ which generates more number of a’s than b’s which is, n m or morenumber of b’s than a’s which is, n m.Q.24Convert the following grammar into CNF:S aB bAA a aS bAAB b bS aBBSolution:Refer to the example 5.41 from the book.Q.25Write the CFG for the language:L {a2n bn n 1}Solution:The CFG can be written as,S aaSb aab@ Oxford University Press 2013. All rights reserved.11

Theory of ComputationQ.26Solutions for review questionsWhat is an ambiguous grammar? Explain with the help of an example, the removal of ambiguityin CFGs.Solution:Refer to the section 5.8.Q.27Convert the following CFG into CNF:S aSa bSb a b aa bbSolution:Refer to the example 5.40 from the book.Q.28Write a short note on Chomsky hierarchy.Solution:Refer to the section 5.11.Q.29Find the context-free grammar with no useless symbols equivalent to:S AB CaB BC ABA aC aB bSolution:As we can see, symbol B does not always derive string of all terminals. Look at the production rules forB, that are, B B C A B. Both C and A can derive string of terminals. Hence, B is a useless symbol. Weneed to remove symbol B and all its usage from the above CFG to get,S A CaA aC bQ.30If the grammar G is given by the productions:@ Oxford University Press 2013. All rights reserved.12

Theory of ComputationSolutions for review questionsS a S a b S b a a b b ,Show that L(G) has no strings of odd length.Solution:Let us try deriving strings with their increasing string lengths.The minimal length, i.e., zero length string is ‘ ’. This is an even length string, zero being the evennumber.The next level strings which are directly derivable from start symbol S are, ‘aa’ and ‘bb’. These havelength two which is also a even number.Consider the below derivations,S a S aS a S aS a b S b aS a b S b aS a b b aS a b a a b aIt always adds the even length using the remaining productions for S.Thus, the language L(G) has no strings of odd length.Q.31Construct a DFA equivalent to the following grammar:S aS bS aAA bBB aCC bA Solution:As there is a self-loop on the start symbol, let us introduce a new start symbol T. The modified CFG is,T SS aS bS aAA bBB aCC bA @ Oxford University Press 2013. All rights reserved.13

Theory of ComputationSolutions for review questionsThe NFA corresponding to the above CFG is as shown in the figure below.This is NFA with -transitions and can be directly converted to the equivalent DFA.We have relabelled the states from 1 to 6. The STF for the DFA is,Q\ ab123224323454*526654We can see that the states (1, 3) and (4, 6) are equivalent. To obtain the reduced DFA we can removestates 3 and 6 and replace all occurrences of them by 1 and 4 respectively. The reduced STF is,@ Oxford University Press 2013. All rights reserved.14

Theory of ComputationSolutions for review questionsQ\ ab121224454*524This STF cannot be reduced further and hence the STF for the final DFA required. The TG for the DFAis,Q.32Construct a regular grammar for the DFA shown in Fig. 5.28.Figure 5.28Solution:The grammar required is,q0 a q1 b q0 q1 a q2 b q2q2 bq2 a q0Q.33Convert the following grammar into its equivalent GNF:S A B; A B S b; B S A a@ Oxford University Press 2013. All rights reserved.15

Theory of ComputationSolutions for review questionsSolution:Refer to the example 5.44 from the book; replace S A1, A A2, B A3.Q.34Show that the following grammar is ambiguous:S a abSb aAbA bS aAAbSolution:We need to show at least two different derivations for the same string to show that the given CFG isambiguous. One such string is ‘abab’. Below are two different leftmost derivations for the string. abSb abab aAb abSb ababSSAs there are two different ways to derive the same string, the grammar is ambiguous.Q.35Describe the terms ‘left-linear’ and ‘right-linear’ grammars; and convert the following left-lineargrammar to its equivalent right-linear grammar.S B1 A0 C0A C0 A1 B1 0B B1 1C A0Solution:Refer to the section 5.11.4 for details on left-linear and right-liner grammars. Refer to the example 5.48from the book.Q.36For the following grammar, find an equivalent grammar, which is in reduced form and has no unitproductions.@ Oxford University Press 2013. All rights reserved.16

Theory of ComputationSolutions for review questionsS ABA aB C bC DD EE aSolution:Substitute for E in production for D to reduce the unit production ‘D E’.S ABA aB C bC DD aSimilarly, substituting for D we get,S ABA aB C bC aWe can get rid of another unit production ‘B C’ the similar way,S ABA aB a bFurther simplification gives us,S aBB a bThe final simplified grammar without any unit productions is,S aa ab@ Oxford University Press 2013. All rights reserved.17