The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 9 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Week 9
At the end of this tutorial, you will be able to
• construct a grammar given an automaton;
• design Context Free Grammars
• construct an automaton given a grammar;
• design push-down automata given a language; • show that a given grammar is ambiguous.
• convert a Context Free Grammar to a Push-down Automata.
Exercise 1 From Grammars to Automata
The following right linear grammar describes a language of binary strings that begin and end with the same bit:
S0→ 0S1 |1S2 |0S3 |1S3 S1→ 0S1 |1S1 |0S3
S2→ 0S2 |1S2 |1S3
S3 → ε
where S0 is the start symbol.
1. Use the algorithm presented in lectures, convert this right linear grammar to a NFA.
Note that the final state Sf in the algorithm does not play any role in this case, so you can safely delete it.
Solution.
0,1
? S1
Q0
06Q
Q
Q
0 , 1 Q Qs
– S0 – S3
3
1
? 1
S2
6
0,1
1
2. If you need more practice with finite automata, use the subset construction algorithm to construct an equivalent DFA from your previous answer.
Solution.
0
?
-
1 0
S1 1
S13
–
06
S0
1
?
-
0 1
S2 0
S23
Exercise 2
From Automata to Grammars
6
1
Consider the non-deterministic finite automaton A:
-S0
Q Q
Q 1Q
T
3 0
6
U 0,1
1. Describe the language that this automaton accepts.
Solution. The language L(A) is the set of all binary integers that are even (or, equivalently, end in 0) and have no
unnecessary leading 0s.
2. Following the algorithm presented in lectures, give a right-linear grammar accepting the same language.
Solution.
S → 0T | 1U T→ε
U → 0T | 0U | 1U
3. Can you see a simpler right-linear grammar that would accept the same language?
Solution. There are no transitions out of the final state T , so we could eliminate it and use the smaller grammar:
S → 0 | 1U
U → 0 | 0U | 1U
Qs
2
Exercise 3 Deterministic PDAs
Consider the context-free grammar
Exercise 4
Deterministic Pushdown Automata
block → decls → stmts →
begin decls stmts end dec ; | decls dec ;
st | st ; stmts
where {begin, end, dec, ;, st} are the terminals, and block is the start symbol. 1. Derive a (non-deterministic) PDA from this grammar.
Solution.
Solution.
(S0, begin dec; dec; st end, Z)
⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S1, ⇒(S2, ⇒ accept
begin begin
dec; dec; dec; dec; dec;
;
dec; dec; dec; dec; dec; dec; dec;
;
st end, st end, st end, st end, st end, st end, st end, st end, st end, st end,
end, ε, ε,
blockZ) begin decls stmts end Z) decls stmts end Z) decls dec ; stmts end Z) dec;dec;stmtsendZ) ;dec;stmtsendZ)
δ(S0,ε,Z) → S1/blockZ δ(S1,ε,block) → S1/begindeclsstmtsend
δ(S1,ε,decls) → S1/dec; δ(S1,ε,decls) → S1/declsdec; δ(S1,ε,stmts) → S1/st δ(S1,ε,stmts) → S1/st;stmts
δ(S1,x,x) → S1/ε δ(S1,ε,Z) → S2/ε
(forallx∈{begin,end,dec,;,st})
with start state S0 and final state S2.
We used the variable x above to compress five transitions (for each non-terminal) into one. This is fine to do e.g. to
save time in an exam as long as you are completely clear and explicit about the meaning of your abbreviations. 2. Give a trace to show that your PDA accepts the string: begin dec; dec; st end
Design a deterministic push-down automaton that recognises language L and give the transition function of the automaton. L = {w# | w ∈ {(, )}∗ and w is a well-parenthesised string}.
Here the alphabet is {(, ), #}, e.g (()())()# belongs to the language, and (()(#)() does not belong. Solution.
δ(S0,(,Z) δ(S0,#,Z) δ(S1,(,a) δ(S1,(,Z) δ(S1,),a) δ(S1,#,Z)
→ S1 /aZ
→ S2 /ε
→ S1 /aa
→ S1 /aZ
→ S1 /ε
→ S2 /ε
3
dec
; stmts end Z ) ; stmts end Z) stmts end Z) st end Z) endZ) Z) ε)
(, Z/aZ (, a/aa
#, Z/ε
S0 S1
), a/ε
Ambiguity
S → aSbS|bSaS|ε
1. Show that this grammar is ambiguous by constructing two different parse trees for abab.
Exercise 5
Consider the grammar
Solution.
start
SS
zz $$ ** zz $$ ** aSbS aSbS
zz $$ ** zz $$ ** $$ εaSbSbSaSε
εεεε
2. Describe the language this grammar generates.
Solution. This grammar generates the language of all strings over {a, b} with the same number of as and bs.
3. Optional and hard: Give a formal proof of the fact that the language generated by this grammar is indeed the language that you have identified above.
Solution. One direction is easy: every sentential form produced by this grammar has an equal number of as and bs, so the language specified by this grammar must be included in the language of strings with an equal number of as and bs.
The other direction – showing that all strings with an equal number of as and bs can be derived by this grammar – is a bit harder. The proof is by induction on the length of strings: assume that for all strings s shorter than the given string, if s has equal numbers of as and bs, then s is generated by the grammar.
Let the given string be s, with equal numbers of as and bs. If s = ε this is easy; assume s is non-empty. Write s = αβ where α is as short as possible, but non-empty, such that each of α and β have equal numbers of as and bs (β may be empty). Suppose the given string s (and α) starts with a. Then α ends with b (why? — you work this one out!).
Then write s = aα′bβ: by induction both α′ and β are generated by the grammar. Therefore, using the first production for S, s = aα′bβ is generated by the grammar.
(If α started with b then exactly equivalent reasoning would hold, using the second production for S).
Incidentally, you may be wondering if there exists any unambiguous grammar for this language. The answer is yes, but the simplest example I’ve found uses 7 non-terminals and 17 productions – rather an increase on 1 and 3! This shows that disambiguating a grammar can in general be quite difficult.
Exercise 6
Consider the grammar:
S → ¬S|S∨T|T T → T∧U|U
U → (S)|true|false
1. Demonstrate that this grammar is ambiguous.
Operator Precedence
4
Solution. There are two parse trees for ¬ true ∨ false, for example: SS
xx ” xx S∨T¬S
&& xx && ¬SUS∨T
T false T U
U U false
true true
2. Modify the grammar to eliminate the ambiguity and to reflect the normal precedence for logical operators (¬ binds the tightest, then ∧, then ∨.)
S Solution. T U
→ S∨T|T
→ T ∧ U | U There are other answers possible here; for example we could have → ¬U|(S)|true|false
another non-terminal V to handle the brackets at a ‘lower’ level than the negation (it turns out that this is not necessary).
Exercise 7 Context-Free Grammars and Automata
1. Give a context free grammar H that generates the language
M ={ambn |2m>n>m}.
Hint:mcan’tbe0,becauseinthatcase2m = m.mcan’tbe1,becauseinthatcase2 > n > 1,suchanatural number n doesn’t exist. So the shortest string in the language M is aabbb. For longer strings, you need to make sure that the number n of bs and the number m of as satisfy 2m > n > m.
Solution. It is impossible for the number of as to be less than two, so the grammar below starts off by adding two as and three bs, then proceeds by adding either one or two bs for each a added.
S →aaTbbb
T →ε|aTb|aTbb
where S is the start symbol.
This is not the only correct answer – most context-free languages are definable via many different context-free grammars, and the language M is no exception to this. Of note, the grammar above is ambiguous (see below); designing an unambiguous grammar for M is an worthwhile exercise.
2. Using the grammar H you defined above, draw a parse tree for the string a4b6, i.e., aaaabbbbbb. Solution. For the grammar above either of these trees are correct:
SS
ww ” )) ww ” )) aaTbbbaaTbbb
” aTb aTbb
” aTbb aTb
εε
3. Consider the following context free grammar in the lectures: 5
Exercise 8
More on Deterministic Pushdown Automata
1. {an ban |n≥0}; Solution.
→ S0 /aZ → S0 /aa → S2/ε → S1 /a → S1 /ε → S2 /ε
T → UV
U → aUb | ε V → cV | ε
W → XY
X → aX | ε Y → bYc | ε
δ(S0,a,Z) δ(S0,a,a) δ(S0,b,Z) δ(S0,b,a) δ(S1,a,a) δ(S1,ε,Z)
to accept immediately if string is b
Initialisation: Non-terminals:
δ(S0,ε,Z) δ(S1,ε,S) δ(S1,ε,S) δ(S1,ε,T) δ(S1,ε,U) δ(S1,ε,U) δ(S1,ε,V) δ(S1,ε,V) δ(S1,ε,W) δ(S1,ε,X) δ(S1,ε,X) δ(S1,ε,Y) δ(S1,ε,Y) δ(S1,x,x) δ(S1,ε,Z)
→ S1/SZ
→ S1 /T
→ S1 /W
→ S1/UV
→ S1/aUb
→ S1/ε
→ S1 /cV
→ S1/ε
→ S1/XY
→ S1 /aX
→ S1 /ε
→ S1/bYc
→ S1/ε
→ S1 /ε
→ S2 /ε
Terminals: Termination:
(S0, abbcc, Z)
⇒ (S1, abbcc, SZ)
⇒ (S1, abbcc, W Z) ⇒ (S1, abbcc, XY Z) ⇒ (S1, abbcc, aXY Z) ⇒ (S1, bbcc, XY Z) ⇒ (S1, bbcc, Y Z)
⇒ (S1 , bbcc, bY cZ ) ⇒ (S1, bcc, Y cZ)
⇒ (S1 , bcc, bY ccZ ) ⇒ (S1, cc, Y ccZ)
⇒ (S1 , cc, ccZ )
⇒ (S1,c,cZ)
⇒ (S1,ε,Z)
⇒ (S2,ε,ε)
Accept.
S→T|W
Convert this grammar to a (non-deterministic) PDA and give the transition relation of the PDA.
Solution. The constructed (non-deterministic PDA) has an initial state S0, with the following transitions:
where x ∈ {a, b, c}.
4. Give a PDA trace for processing the string abbcc using the PDA you constructed in the previous question. State
whether the string is accepted or rejected.
Solution. The PDA trace for processing the string abbcc is as below.
For each of the following languages, design a deterministic push-down automaton that recognises the language and give the transition function of the automaton.
6
start
a, Z/aZ
a, a/ε
S0 a, a/aa
b, a/a
S1 b, Z/ε
ε, Z/ε
S2
2. {anbmambn |m>0∧n>0}; Solution.
→ S1 /aZ → S1 /aa → S2 /ba → S2 /bb → S3 /ε → S3 /ε → S4 /ε → S4 /ε → S5 /ε
start
S0
δ(S0,a,Z) δ(S1,a,a) δ(S1,b,a) δ(S2,b,b) δ(S2,a,b) δ(S3,a,b) δ(S3,b,a) δ(S4,b,a) δ(S4,ε,Z)
a, Z/aZ
ε, Z/ε
a, a/aa
S1
b, a/ε
b, a/ba
b, a/ε
b, b/bb
S2
a, b/ε
start
S5 S4 S3
a, b/ε
S2
We can come up with a more optimised PDA:
a, Z/aZ a, a/aa
S0 b, a/ba
b, b/bb
a, b/ε
b, a/ε
S1 a, b/ε
ε, Z/ε
7