EXAM Preparation Phase I + Feedback PDF

Preview

Summary

Warning: Popup annotation has a missing or invalid parent annotation. Warning: Popup annotation has a missing or invalid parent annotation. Warning: Popup annotation has a missing or invalid parent annotation. Warning: Popup annotation has a missing or invalid parent annotation. Warning: Popup annot...

Description

Question 1: Build a DPDA to show that the language L = {(ab)n(ba)n - 2 | n > 2 } is deterministic context free Feedback on Question 1 The DPDA presented in Figure 1 starts by reading n ab-substrings (READ1 - READ2). For each absubstring read, an X is pushed onto the stack (PUSH X). If we are in READ1 and a b is read then we move to READ3 where we read an a before we start popping X’s. Thus after we have read the first ba-substring we’ll pop three X’s (POP1;POP2; POP3). One X is popped for the ba-substring that has just been read. The other two X’s are popped to account for the two extra ab-substrings that should be present in the input string if the input string is to be accepted. Note that the shortest word to be accepted is abababba. Thus the smallest number of X’s to be popped from the stack corresponds to the smallest number of ab-substrings that must be present in a word belonging to L. Starting at READ4 we enter a loop READ4-READ5-POP3 where, for every ba-substring read, an X is popped from the stack. If the READ4-READ5-POP3 loop is entered then the remainder of ba-substrings should be exactly equal to the number of X’s on the stack. If we read Δ in READ4 then the end of the input string has been reached. POP4 checks the tape for emptiness. If the stack is also empty then we accept the input string.

Figure 1: DPDA of the language L = {(ab)n(ba)n - 2 | n > 2 }

Question 2: Draw a DPDA that accepts the language L = {aa(bb)n an – 2 |n > 2} Feedback on Question 2

a

Figure 2: DPDA of the language L = {aa(bb)n an – 2 |n > 2} The language here consists of words where the first part of the word is aa, then 3 or more occurrences of the string bb and then as (where there are two fewer as than there are bb substrings). For example, the word aabbbbbba is a valid word in this language as we can rewrite this as

aa(bb)3a1

where n = 3 (> 2). This is in fact the smallest word in this language. A DPDA which recognises words of this form is shown in Figure 2 above. This DPDA essentially has a number of “components” • one to recognise the first substring aa;

• one to read the bb substrings and push an X each time one of these is encountered; • one to read as and count off each a against an X • one to check that there are two more Xs on the stack than there are as in the input string and • finally, a component to check that the stack is empty at the same time as the input string is empty.

Question 3: Build a DPDA that accepts the language L ={(ab)n aab (b)2n| n>=0}

Feedback on Question 3 BuildaDPDAthatacceptsthelanguageL={(ab)naab(b)2n|n>0}. Observethatthelanguageisarepetitionofthesubstring“ab”followedbythestring“aab” followed bytwiceasmany“b”sas“ab”s.Thisisthussimilartothetextbookexample whereaspecial marker“X”wasused. LetusdefinetheDPDA: 1.∑={ab} 2.┌={ab} 3.TapeofinfinitelengthcontainingastringdefinedbyL 4.Theemptypushdownstack 5.Thestatesasdefinedonpage307ofthetextbook. Noticeinparticularthatwhenn=0,thesequenceofeventsissimplytoreadana,read another a,readab,andreadΔ.ThisalsomatchesthelanguagedefinedbyL,sinceforn= 0,L={aab}. Also,wedon’tbotherpushingaontothestack,theideaistomatcheveryreadb,with everyb poppedfromthestack.

Figure3:DPDAofL={(ab)naab(b)2n|n>0}

Question 4: Build a DPDA to show that the language L = {(ab)naaa(ba)n - 2 | n > 2 } is deterministic context free.

Feedback on Question 4 Thesmallestwordinthislanguageiswhenn=3.Thiswordisabababaaaba.Allwordsin this languagestartwiththreeormoreabsandendwithoneormorebaswherethereare alwaystwo moreabsthanbas. ThetricktoshowingthatthislanguageiscontextfreeistousethePDAto“match”the occurrences ofabtotheoccurrencesofbawhichappearlaterinthestring.Weshould alsotakecareofthefact thattherehavetobetwomoreabsthanbasbuttherehastobe atleastoneba(andthreeabs). Theaaastringinthemiddleisaseparatoranddoesnotaffectthedecisionofwhetheror notthe languageiscontextfree. OurPDAcanthusbeoutlinedas 1.Readtwoinstancesofab(butdonothingtothestack).Thesearetheextraabsthatwe can simplygetridofbecauseweknowthereshouldbeexactlytwoofthem. 2.Readinoneinstanceofab(thismatcheswiththeonerequiredba). 3.ReadinadditionalinstancesofabandforeachsuchinstancepushanXontothestack. Here weareessentiallycountinghowmanyabswehave. 4.Readinaaa(butdonothingtothestack). 5.Readintheonerequiredba. 6.ReadininstancesofbaandforeachinstancepopanXoffthestack.Hereeachbais ticked offagainstanabthatwasreadatthebeginningofthestring. 7.Whenallofthebashavebeenreadthencheckthattheinputstringandthestackare both empty. WecannowbuildaPDAtodothis. ThePDAisshowninFigurebelow. ThephasesoutlinedabovecanbeseenquiteeasilyinthelayoutofthePDA.

Figure 4: DPDA of L= L = {(ab)naaa(ba)n - 2 | n > 2 }

Question 5: Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0 } is deterministic context free. Feedback on Question 5 Figure shows a DPDA which recognises the language. In this DPDA the first ab substring (which must exist by the definition of the language) is read and an X is pushed onto the stack. Then subsequent ab substrings are read until the first b in the first ba substring is read at which point the second part of the DPDA starts working to recognise the ba substrings. An X is popped off the stack for each ba found. When the first a of the aa substring is read the DPDA reads the next a and then checks that all the Xs have been popped off the stack. If there were still any Xs on the stack then the number of ab and ba substrings would not have been the same and the word would not be in the language. Check using other words in the language that the DPDA is correct.

Figure 5: DPDA of the language L = {(ab)n(ba)naa | n > 0 }

Question 6: Draw a DPDA that accepts the language L = {an+2bban – 2 |n > 1} Feedback on Question 6 The shortest word belonging to L is aaaabb. The second shortest word is aaaaabba.

The difference between the first group of a’s and the second group of a’s is 4. All words belonging to L have a bb-substring. We present a DPDA in Figure below below that accepts L. The given DPDA read the first clump of a’s and push an X for each a read onto the stack until the first b is read. If the first b is read our DPDA branch to a next POP-state where an X is popped from the stack. Another POP-state is reached and a second X is popped from the stack. We reach the next READ-state where the second b from the bb-substring is read. Two X’s are in turn popped from the next two POP-states. Thus to get the number of X’s (representing the number of a’s of the first group of a’s) on the stack equal to the number of a’s (of the clump of a’s after the bb-substring) on the tape we pop four a’s from the stack. We have decided to pop two a’s for every b read. (You could, however, also pop four a’s after you have read the bb-substring.) Proceeding with the DPDA presented in figure below we enter a loop where we pop an X from the stack for each a read on the tape until we read Δ. If Δ is read then we should pop Δ from the stack too, to ensure that the stack is empty. Do you agree that the DPDA provided in Figure accepts all the words belonging to L and no words in L.

Figure 6: DPDA of the language L = {an+2bban – 2 |n > 1}

Question 7: Draw a deterministic pushdown automaton (DPDA) that accepts the language L = {(aa)n (bab)n-1 | n >=1 } Feedback on Question 7

Figure

7: DPDA of the language L = {(aa)n (bab)n-1 | n >=1 }...