11m ago

66 Views

16 Downloads

479.33 KB

28 Pages

Transcription

Theory of ComputationSolutions for review questionsAuthor: Vivek Kulkarni( vivek [email protected] )Chapter-5: GrammarsSolutions for Review [email protected] 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 [email protected] 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 [email protected] 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)[email protected] 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 [email protected] 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 [email protected] 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 [email protected] 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 [email protected] 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 [email protected] 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 [email protected] Oxford University Press 2013. All rights reserved.17

Theory of ComputationQ.37Solutions for review questionsGive the regular expression for the language generated by the following grammar:S A B; A 0A ; B 0B B Solution:We can see that the unit production ‘B B’ is redundant and can be removed without changing themeaning. We get,S A BA 0A B 0B As we can see both A and B generate the regular language 0*. Hence, the language generated by thegrammar where S is the start symbol is,0* 0* 0*Q.38For the following grammar G, construct an NFA M such that L(M) L(G):S abA baBA bS bB aS aSolution:Let us first rewrite the CFG in the form suitable to draw the NFA.S aT bUT bAU aBA bS bB aS aNow, we can draw the NFA equivalent to the above CFG as shown in the figure [email protected] Oxford University Press 2013. All rights reserved.18

Theory of ComputationQ.39Solutions for review questionsShow that the following language L is a CFL.L {0 1 n 1} {0 12n n 1}nnnSolution:{0 1 n 1} is a CFL as we know and so is {0 12n n 1}. As per closure properties of CFLs, these arennnclosed under union operation and hence, L is a CFL.Let us try to write CFGs for both the above language parts. The CFG for {0n 1n n 1} is,A 0A1 01The CFG for {0n 12n n 1} is,B 0B11 011Hence, the CFG for L can be written as,S A BA 0A1 01B 0B11 011Thus, L is a CFL.Q.40Construct the right-linear grammar corresponding to the regular expression:R (0 1)* (1 (01)*)Solution:S [email protected] Oxford University Press 2013. All rights reserved.19

Theory of ComputationSolutions for review questionsA 0A 1A , represents (0 1)*B 01B , represents (01)*C B 1, represents (1 (01) *)Let us try writing this in the right-linear grammar format.S 0S 1S B 1This can be further rewritten as,S 0S 1S 01T 1 T 01T Q.41Convert the following grammar to Greibach normal form (GNF):S B S; S A a; A b c; B A cSolution:Let us substitute for A and B in S. We get,S AcSS bcaA bcThis further can be simplified as,S bccSS bcaThis can be further updated to rewrite in GNF as below,S bTS bUT cVU cXV cSX aQ.42Show that the following languages are context-free [email protected] Oxford University Press 2013. All rights reserved.20

Theory of ComputationSolutions for review questions(1)L1 {ai bi cj i, j 1}(2)L2 {ai bj cj i, j 1}Solution:Let us try writing the CFGs for these languages.(1)iijijjThe CFG for the language, L1 {a b c i, j 1} is,S A CA a A b a bC c C c(2)The CFG for the language, L2 {a b c i, j 1} is,S A CA a A aC b C c b cQ.43Find whether the string ‘aabbb’ is a member of L(G), where G is defined as:S XYX YY aY XY bSolution:Let us try deriving the string ‘aabbb’ using the given grammar. Below is the rightmost derivation for thestring.S XY XXY XXb XYYb XYbb XXYbb [email protected] Oxford University Press 2013. All rights reserved.21

Theory of ComputationSolutions for review questions Xabbb aabbbHence, from the above derivation, we can say that 'aabbb' is a member of L(G).Q.44Is the following CFG is ambiguous?G {(S, A), (a, b), P, S}, where P consists of:S aAS aA SbA SS baSolution:Let us consider the string ‘aaaaaaa’ that can have at least two different derivations. Hence, the grammar isambiguous.Q.45Convert the following grammar to Greibach normal form, assuming A1 as the start symbol.A1 A2 A3A2 A3 A1 bA3 A1 A2 [email protected] Oxford University Press 2013. All rights reserved.22

Theory of ComputationSolutions for review questionsSolution:Refer to the example 5.44 from the book.Q.46Find context-free grammars generating each of the following languages:(1)L1 {ai bj ck i j k}(2)L2 {ai bj ck j i k}(3)L3 {ai bj ck i j or j k}Solution:(1)Refer to the example 5.19 from the book.(2)The CFG for the language, L2 {ai bj ck j i k} is,X SAS aSb A bAc (3)ijkThe CFG for the language, L3 {a b c i j or j k} is,P X Y(Below 3 production cater to the condition ‘i j’)X SCS aSb C cC (Below 3 production cater to the condition ‘j k’)Y ATA cA T bTc Q.47Draw an NFA that accepts the language generated by the following grammar, and explain thelanguage it generates.S a A b C bA a S b BB a C b A aC a B b [email protected] Oxford University Press 2013. All rights reserved.23

Theory of ComputationSolutions for review questionsSolution:The NFA equivalent to the above grammar is,The language generated by the given grammar G is,L(G) {b, aab, baa, aba, bbb, aabaa, }Each string in the language is of odd length and contains even number of a’s.Q.48What is a normal form? Explain Chomsky normal form (CNF) and Greibach normal form (GNF)with the help of suitable examples.Solution:Refer to the section 5.10.Q.49Find the context-free grammar generating the following languages:(a)The set of odd length strings in {a, b}* having a as the middle symbol(b)The set of even length strings over {a, b}* whose middle symbols are sameSolution:(a)The CFG for the ‘set of odd length strings in {a, b}* having a as the middle symbol’ is,S B a BB a B b B a b(b)The CFG for the ‘set of even length strings over {a, b}* whose middle symbols are same’ is,S B a a B B b b BB a B b B a [email protected] Oxford University Press 2013. All rights reserved.24

Theory of ComputationQ.50Solutions for review questionsConvert the following CFG into Greibach normal form (GNF):S AB 0A BX 1B CD 2C AD 0D 1Solution:In the above grammar X is a useless symbol. Hence, we need to remove all the production it is part of.Simplifying the grammar without useless symbols is,S AB 0A 1B CD 2C AD 0D 1Substitute for A in the above grammar to get,S 1B 0B CD 2C 1D 0D 1Substituting C in B we get,S 1B 0B 1DD 0D 2C 1D 0D 1We need not simplify the grammar as it is already in GNF.Q.51Construct a CFG for the following sets:(i){a2n bc n 1}(ii){an bm cm dn m, n 1}@ Oxford University Press 2013. All rights reserved.25

Theory of ComputationSolutions for review questionsSolution:(i)The CFG for the language, {a2n bc n 1} is,S AbcA aaA aa(ii)The CFG for the language, {an bm cm dn m, n 1} is,S aSd AA bAc bcQ.52Convert the following CFG to Chomsky normal form:S AACDA aAb C aC aD aDa bDb Solution:CNF has either two non-terminals or a single terminal symbol on the right hand side of every productionrule. The above CFG can be written in CNF as below,S ATT AUU CDA PR C PC aD PV QW P aQ bR AQV DPW DQQ.53iShow that the language L {02 i 1} is not a [email protected] Oxford University Press 2013. All rights reserved.26

Theory of ComputationSolutions for review questionsSolution:Step 1: Let us assume that the language L is a CFL.Step 2: Let us choose a sufficiently large string z such that z 0l for some large l. Since we assumed thatL is a CFL and an infinite language; pumping lemma can be applied now. This means that we should beable to write a string: z uvwxy.Step 3: As per pumping lemma, every string ‘uviwxiy’, for all i 0 is in L.That is, if we consider i 0, then uv0wx0y uwy is in L. Let us assume uwy is a perfect power of 2, sayk.As per pumping lemma, let us have vx r 1; and let i k. Then, as per pumping lemma, ‘uvkwxky’should be in L. However, uvkwxky uwy k * vx k k * r k (1 r), which is not always aperfect power of 2. Thus, ‘uvkwxky’ is not in L. This contradicts our assumption that L is a CFL. Hence, Lis not a CFL.Q.542Using pumping lemma, show that the language L {0i i 1} is not a CFL.Solution:Step 1: Let us assume that the language L is a CFL.Step 2: Let us choose a sufficiently large string z such that z 0l for some large l, which is a perfectsquare. Since we assumed that L is a CFL and an infinite language; pumping lemma can be applied now.This means that we should be able to write a string: z uvwxy.Step 3: As per pumping lemma, every string ‘uviwxiy’, for all i 0 is in L.That is, if we consider i 0, then uv0wx0y uwy is in L. Let us assume uwy is a perfect square, say k.As per pumping lemma, let us have vx r 1; and let i k. Then, as per pumping lemma, ‘uvkwxky’should be in L. However, uvkwxky uwy k * vx k k * r k (1 r), which is not always [email protected] Oxford University Press 2013. All rights reserved.27

Theory of ComputationSolutions for review questionsperfect square number. Thus, ‘uvkwxky’ is not in L. This contradicts our assumption that L is a CFL.Hence, L is not a [email protected] Oxford University Press 2013. All rights reserved.28

Theory of Computation Solutions for review questions @ Oxford University Press 2013. All rights reserved. 1 Aut