Assignment 2 solutions PDF

Preview

Summary

Warning: TT: undefined function: 32COS 37 01/2 02 /1/2 020Tutorial Letter 202 /1/20 20Theoretical Computer Science IIICOSSemester 1School of ComputingSample solutions to Assignment 02BAR CODE Define Tomorrow. univof south africaersity Question 1Build a DPDA to show that L = {(ab)n+2 (ba)n aa | n &am...

Description

COS3701/202/1/2020

Tutorial Letter 202/1/2020

Theoretical Computer Science III

COS3701 Semester 1 School of Computing

Sample solutions to Assignment 02

BAR CODE

Define Tomorrow.

univer sity of south africa

Question 1 Build a DPDA to show that L = {(ab)n+2 (ba)n aa | n > 0} is deterministic context-free. The DPDA presented in Figure 1 star ts by reading n + 2 ab -substrings. Note that as n > 0 there must be at least 3 of these substr ings – the smallest word in this language is (ab)3 (ba)1aa. For each ab-substring re ad an X is pushed onto the stack. If we are in the first read and a b is read then the DPDA branches to reading a ba substring. After this substring is read, the DPDA pops two X s to get rid of the two X s for the first two (extra) ab substr ings. The DPDA then pops another X which matches the third ab substring. If the DPDA is processing the smallest word then an a is the next input character. If this is read then another a is expected. After the second a is read then there shou ld be no further input characters and there should be nothing on the stack. If this holds then the DPDA accepts the str ing. If the word being pro cessed is not the shortest word then more copies of the ba string must be read and for each of these an X is popped off the stack. When an a is encountered (instead of a b ) then the DPDA checks for the aa substring and then empty input and empty stack as for the shortest word. Check using other words in the language that the DPDA is correct.

Figure 1: A DPDA to recognise L = {(ab)n+2 (ba)naa | n > 0 }

COS3701/202

Question 2 Use the pumping lemma with length to prove that L = {a nb 3nan | n > 0} is not context free. The alphabet is Σ = {a, b }. 1. The first step is to assume that the language L = {a n b 3n an | n = 1; 2; 3; ... } actually is contextfree. This means that there exists a CFG in Chom sky Normal Form (CNF) with, say, p live productions which generates the language. Because we assume that the language is context free, we may apply the pumping lemma. According to the pumping lemma with length any word w in L with more than 2p characters can be broken up into five parts, i.e. the word can be written as w = uvxyz , with length(vxy ) ≤ 2p and length(x) > 0 and length(v ) + length(y) > 0 and where all words of the form uv n xy n z with n > 1 are also in the language. p

p

p

2. We should next choose a suitable word from L which is long enough. The word a2 b3.2 a2 seems a good choice: it is in L and it has more than 2 p characters. Let us examine all the p p p different ways in which the word a2 b3.2 a2 can be divided up into five parts. Remember that vxy cannot have more than 2p characters. This means that there are five ways in which vxy can occur in the word: (a) fully from the first 2p characters (thus consists of as only), (b) covering some of the first as and also some of the bs, (c) fully from the group of b s, (d) covering some characters of the group of b s and some characters of the final group of as, (e) fully from the second group of as. We now examine each of these five possibilities. We are going to show that the pumped word will in none of these cases be of the form an b 3na n. (a) Suppose vxy consists of as only from the first group of as. According to the pumping lemma with length the word uvvxyyz must also be in the language L. This word will now p p have more than 2p as at the beginning of the word followed by b3.2 a2 and will not be of the form an b 3na n. Such a word is not in L. (b) Suppose vxy consists of as followed by b s. According to the pumping lemma with length the word uvvxyyz must also be in the language L. What will this (pumped) word look like? Well, there are several possibilities. • If v consists of as only and y consists of b s only, the pumped word will have more than 2 p as at the beginning of the word followed by more than 3.2p b s, followed by p a2 . The word is not of the form an b 3nan and is thus not in L. • If v consists of as and bs, and y of b s only, the pumped word will have more than 2p as followed by mo re than 3.2p b s, followed by 2p as. There will also be more ab-substrings than allowed. The word is not of the form an b 3nan and thus not in L. • The same problem will occur if v consists of as only and y consists of as and bs, because the pumped word will have more than 2p as, followed by more than 3.2p b s 11

and more than 2 p as followed by a2p . There will also be more ab-substrings than allowed. The word is not of the form a nb 3nan and thus not in L. • In any of the above mentioned three possible cases either v or y may be empty (both cannot be empty – are you able to explain why not?), but still the pumped word will not be a permissible word in L. (c) Suppose vxy consists of b s only. According to the pumping lemma with length the word uvvxyyz must also be in the language L. This word will now have 2 p as at the beginning p followed by more than 3.2 p b s and then a2 . Such a word is, however, not in L, because 3n it is not of the form an b an . (d) Suppose vxy consists of b s followed by as. According to the pumping lemma with length the word uvvxyyz must also be in the language L. What will this (pumped) word look like? Well, as in case (b) above we have several possibilities. • If v consists of bs only and y consists of as only, the pumped word will have 2p as at the beginning of the word followed by more than 3.2 p b s and mo re than 2p as. The word is not of the form an b 3nan and thus the pumped word will not be in L. • If v consists of bs and as and y consists of as only, the pumped word will still star t with 2p as and then have more than 3.2p b s and mo re than 2p as in the last group of as. There will also be more ba-substrings than allowed. The word is not of the form an b 3nan and thus not in L. • The same problem will occur if v consists of b s only and y consists of b s and as, because the pumped word will still start with 2p as followed by more than 3.2p b s and then more than 2p as. There will also be more ba-substrings than allowed. Thus again the word is not in L. • In any of the above possible cases either v or y may be empty (both cannot be empty – according to the pumping lemma), but still the pumped word will not be a permissible word of L. (e) Suppose vxy consists of as only from the second group of as. According to the pumping lemma with length the word uvvxyyz must also be in the language L. This word will now have more than 2p as in the second group of as. Such a word is, however, not in L, because it is not of the form an b3na n . 3. We have seen that all five possible choices of vxy result in a pumped word uv 2 xy 2 z which cannot be in language L. This, however, contradicts the pumping lemma with length. This means that our original assumption that L is context-free, must be re tracted (because, if it were context-free, each pumped word would also have been in the language according to the pumping lemma). We therefore conclude that the given language L is not context-free.

COS3701/202

Question 3 Chapter 18, no 1(v), p 429 of Cohen We have to use the algor ithm introduced to us by Theorem 42 to decide whether the given grammar generates any words, i.e. whether the language is empty or not. The theorem is summarized in your online study material. The given grammar is as follows: S → AB A → BSB B → AAS A → CC B → CC C → SS A→ a|b C → b | bb Step -1: We have to find out whether S is nullable. We see that it is not the case Step 0: The given grammar is not in Chomsky normal form. Therefore we convert it to CNF. We note that no production is of the form S → t where t is a terminal. S → AB A → BR1 R1 → SB B → AR2 R2 → AS A → CC B → CC C → SS C → ZZ A→ a|b C→b Z→b Step 1: We see that the nonterminal A has a production of the required form, namely A→ a and thus can be eliminated. We eliminate all the productions with A on the le ft including: A → BR1 and A → CC. We replace a ll occurrences of A on the right-hand side with a. Now the grammar looks as follows: S → aB R1 → SB B → aR2 R2 → aS B → CC C → SS C → ZZ C→b Z→b Step 2: We see that S has not been eliminated yet. 11

Step 3: The nontermin al C can be eliminated, so we move to step 1. Step 1: The nontermin al C has a production of the required form, namely C→b and can thus be eliminated. The productions C → SS and C → ZZ have C on the left-hand side and a re eliminated. There is one occurrence of C on the right-hand side – B → CC where C should be replaced with b. The grammar now looks as follows: S → aB R1 → SB B → aR2 R2 → aS B → bb Z→b Step 2: We see that S has not been eliminated yet. Step 3: The nontermin al Z can be eliminated, so we move to step 1. Step 1: The nontermin al Z has a production of the required form, namely: Z→b therefore it can be eliminated. There are no productions that have Z on the left-hand side. There are no other occurrences of Z on the r ight-hand side. The grammar now looks as follows: S → aB R1 → SB B → aR2 R2 → aS B → bb Step 2: Observe S has not been eliminated yet. Step 3: The nontermin al B can be eliminated – we move to step 1. Step 1: The nontermin al B has a production of the required form, namely: B → bb we obtain: S → abb R1 → Sbb R2 → aS Step 2: S has not been eliminated yet. Step 3: The nontermin al S can be eliminated. Step 1: The nontermin al S has a production of the required form, namely: S → abb. we obtain: R1 → abbbb R2 → aabb Step 2: S has been eliminated. We conclude that the CFG generates at least one word. Therefore the CFL is not empty.

COS3701/202

Question 4

Chapter 18, no 10 p 430 of Cohen. We follow the steps of the CYK algor ithm as formulated in the online study material. Note that n = 7. Step 0. We observe that the grammar is in CNF: S → AB | CD | a | b A→ a B → SA C → DS D→b Step 1. Set i = 1. We have seven substrings of length 1. Substring b a b a b a b

All producing nontermin als S (by S → b ) and D (by D → b) S (by S → a) and A (by A → a) S (by S → b ) and D (by D → b) S (by S → a) and A (by A → a) S (by S → b ) and D (by D → b) S (by S → a) and A (by A → a) S (by S → b ) and D (by D → b )

Step 2. i = 7, thus go to step 1. Step 1. Set i = 2. We have only two substrings of length 2. Substring All producing nontermin als ba B (by B → SA ) ab None Step 2. i = 7, thus go to step 1. Step 1. Set i = 3. We have two substrings of length 3. Substring All producing nontermin als bab S , C (by S → CD; C → DS ). aba S , B (by S → AB; B → SA ). Step 2. i = 7, thus go to step 1.

Step 1. Set i = 4. We have two substrings of length 4. Substring All producing nontermin als abab None. baba None. Step 2. i = 7, thus go to step 1. 11

Step 1. Set i = 5. We have two substrings of length 5. Substring Babab ababa

All producing nontermin als S , C, A, B (by S → CD; C → DS; S → AB; B → SA). S , B, A, C (by S → AB; B → SA; S → CD; C → DS).

Step 2. i = 7, thus go to step 1.ep 1. Set i = 6. We have two substrings of length 6. Substring All producing nonterminals None. ababab Bababa None. Step 2. i = 7, thus go to step 1. Step 1. Set i = 7. We have one substring of length 7. Substring All producing nonterminals Babababa S, C, A, B (by S → CD ; C → DS; S → AB; B → SA). Step 2. We see that i = 7(= n) and that S is a producing nonterminal for the word bababab . Thus the word can be generated by the given grammar. The word bababab is generated as follows: S → CD ... step 1 ⇒ DSD(C → DS) ... step 2 ⇒ DABD(S → AB) ... step 3 ⇒ DASAD(B → SA) ... step 4 ⇒ DACDAD(S → CD) ... step 5 ⇒ DADSDAD(C → DS) ... step 6 bababab(S → a; D → b; A → a) ... step 7, 8 and 9

© Unisa 2020...