The Australian National University Research School of Computer Science
Theory of Computation
Release Date. Thursday Mar 12 2020
Due Date. Wednesday March 26 2020, 23.50 Canberra time Maximum credit. 50
Exercise 1 Revisiting the Myhill-Nerode Theorem
Semester 1, 2020 Assignment 1 of 3
(5+5 credits)
Let L be a language over an alphabet Σ. Define the relation RL ⊆ Σ∗ × Σ∗ by (u, w) ∈ RL if the following holds:
∀x ∈ Σ∗(ux ∈ L ⇐⇒ wx ∈ L).
We have seen in the tutorials that RL is in fact an equivalence relation. We denote the equivalence class of x ∈ Σ∗ under this relation by [x] = {y ∈ Σ∗ | (x,y) ∈ RL}. The Myhill-Nerode theorem states the following:
In Tutorial 2 we have proved the direction from left to right. We will now prove the converse direction.
(a) Let L ⊆ Σ∗ be a language and suppose that RL has finitely many equivalence classes. Define the DFA
(Q,Σ,δ,q0,F) by
Q = {[x] | x ∈ Σ∗} δ([x],a) = [xa]
q0 =[ε] F ={[x]|x∈L}
and note that Q is finite by assumption.
(i) Show that δ is well defined, i.e. if [x] = [y], then [xa] = [ya] for all a ∈ Σ.
(ii) Prove by induction that δ([ε], x) ∈ F if and only if x ∈ L.
(b) Prove that the DFA obtained in Part (a) is minimal. That is, given regular language L and a DFA A that accepts precisely L, the state set Q of A has at least as many states as the automaton constucted from RL in Part (a).
Myhill-Nerode Theorem. For any language L we have:
L is regular if and only if RL has a finite number of equivalence classes.
Solution of Exercise 1
Suppose [x] = [y] and let a ∈ Σ. In order to prove that [xa] = [ya] we need to show that for all z ∈ Σ∗, xaz ∈ L iff yaz ∈ L.
So let z be any string in Σ∗. Since we assumed that [x] = [y] we know that for all z′ ∈ Σ∗ we have xz′ ∈ L iff yz′ ∈ L. In particular this holds for z′ = az, hence
xaz=xz′ =yz′ =yaz,
as desired. Since z was arbitrary this proves [xa] = [ya], so δ is well defined.
(ii) Suppose w is equivalent to v. Then it follows from the definition of RL (taking z = ε) that w ∈ L iff v ∈ L. As a consequence, we have
[w]∈F iff w∈L. (1)
CS Help, Email: tutorcs@163.com
(The direction from right to left follows from the definition of F . For the converse, suppose [w] ∈ F, then there is v ∼ w such that v ∈ L and hence by the preceding discussion w ∈ L.) So it suffices to show that
δ([ε], w) = [w] (2)
because then combining (1) and (2) yields the desired result. We prove (2) by induction on
the length of w.
Base cases. If w = ε, then by definition of δ we have δ([ε],ε) = [ε]. If w = a for some
a ∈ Σ, then by definition δ([ε], a) = δ([ε], a) = [εa] = [a].
Step case. Suppose given v ∈ Σ∗ of length ≥ 2 and assume (2) holds for all w ∈ Σ∗ with
|w| < |v| (this is the induction hypothesis). Then w is of the form va for some v ∈ Σ∗ and a ∈ Σ and we have
δ([ε], w) = δ(δ([ε], v), a) (Definition of δ)
= δ([v], a) = [va]
(Induction hypothesis) (Definition of δ) (Because w = va)
This proves (2), hence completes the proof of the question. (b) This solution relies on the following Lemma:
Lemma. Forallx,z∈Σ∗ wehave
δ([x], z) = [xz]. (†) Proof. We proceed by induction on the length of z.
Basecase. Ifz=εthenthisisimmediatefromthedefinitionofδ.Ifz=aforsomea∈Σ
then again the statement follows from the definition of δ.
Stepcase. Weassumethatforallx∈Σ∗ (ofanylength)andforallz′ ∈Σ∗ with|z′|≤k−1
the equation in (†) holds.
Supposez∈Σ∗ haslengthkandwritez=az′,wherea∈Σ.Thenwehave
δ([x], z) = δ([x], az′) (Because z = az′)
= δ([xa], z′)
This completes the proof of the lemma.
(Definition of δ) (By the induction hypothesis) (Because z = az′)
= δ(δ([x], a), z′) (Definition of δ)
We now proceed to the proof of the question. Let [x] and [y] be two different states in Q. Then x and y are not equivalent, so there must exists z ∈ Σ∗ such that precisely one of xz,yz is in L. Without loss of generality assume that xz ∈ L and yz ∈/ L. It follows from Part (a) that
δ([ε], xz) ∈ F and δ([ε], yz) ∈/ F . Hence by the Lemma we have
δ([x], z) = δ([ε], xz) ∈ F and δ([y], z) = δ([ε], yz) ∈/ F. Therefore [x] and [y] are distinguishable.
Since [x] and [y] were chosen arbitrarily, this shows that any pair of states in Q is distinguishable, and hence from the DFA minimisation algorithm from Chapter 4 we conclude that the DFA from Part (a) is already minimal.
Exercise 2 Failure of Pumping Lemma (5+5 credits)
Unlike the Pumping Lemma, the Myhill-Nerode theorem exactly characterises the regular languages. As an illustration, consider the following language:
L={ajckalbm |0≤j≤5andk,l,m∈Nand(k≥2⇒l̸=m)}.
(a) Prove that the Pumping Lemma fails to demonstrate that L is not regular. In detail, demonstrate that there exists n ∈ N such that any string w ∈ L with |w| ≥ n can be written as w = xyz with |xy| ≤ n, |y| > 0 and xyiz ∈ L for all i ≥ 0.
(b) Use the Myhill-Nerode theorem to prove that L is not regular.
Solution of Exercise 2
(a) Letn=7.Letw∈Lsuchthat|w|≥7.Thenwisoftheformalciajbk.Weshallwritewasxyz where |xy| ≤ 7, |y| > 0 and prove that xyiz ∈ L for all i ≥ 0. We consider two cases.
Case 1: k ≤ 1. By the definition of L we have
If0≤j≤5andm≥1thenajckalbm ∈Lforalll,m≥0. (♠)
We split case 1 into two subcases:
Case1A:l=0. Sincej<5andk≤1wehavej+k≤6.Furthermore,becausel=0we must have m ≥ 1, because otherwise |w| < 7. Take x = ajck and y = b (this y exists because m ≥ 1) and z = bm−1. Then clearly we have w = xyz. Moreover, |x| ≤ 6 and |y| = 1 so |xy| ≤ 7 as desired. It follows from (♠) that xyiz = ajckbibm−1 ∈ L for all i ≥ 0.
Case1B:l≥1. Takex=ajck,y=aandz=al−1bm.Clearlywehavew=xyz.By assumption j + k ≤ 6 and hence |x| ≤ 6. As |y| = 1 this implies |xy| ≤ 7, as desired. We have
xyiz = ajckaial−1bm
which is in L for any i ≤ 0 by (♠).
Case2:k≥2. Sincek≥2wemusthavel̸=m.Letx=aj andy=candz=ck−1albm. By definition of L, if l ̸= m and 0 ≤ j ≤ 5 then ajckalbm ∈ L for any non-negative integer m. Therefore xyiz = aj cick−1albm ∈ L for the given x, y, z and any i.
(b) Using the Myhill-Nerode theorem, it suffices to give an infinite number of pairwise non-equivalent strings in L. Consider the collection
{c2at | t ≥ 1}.
We show that every two distinct elements in this collection are non-equivalent. Suppose given c2at and c2as. Since the elements are distinct we must have t ̸= s. Consider bt ∈ Σ∗. We have c2atbt ∈/ L because a and b have the same exponent while c has exponent 2. However, c2asbt ∈ L, because it satisfies the conditions for a string to be in L. This proves that (c2at, c2as) ∈/ RL.
We conclude that RL has an infinite number of equivalence classes, and therefore, by the Myhill- Nerode theorem, the language L cannot be regular.
Exercise 3 DFA-homomorphisms (8 + 2 credits)
In the lectures, we have talked about homomorphisms between languages. Here, we discuss homomor- phisms of automata.
Definition. Let P = (Q,Σ,δ,q0,F) and P′ = (Q′,Σ,δ′,q0′ ,F′) be two DFAs with the same alphabet Σ. A DFA-homomorphism f from P to P ′ is a function f : Q → Q′ which satisfies
(1) f(q0) = q0′ ;
(2) q∈F ifandonlyiff(q)∈F′,forallq∈Q;
(3) f(δ(q,a)) = δ′(f(q),a) for all q ∈ Q and all a ∈ Σ.
(a) For a given automaton P as above, let L(P,q) = {w ∈ Σ∗ | δ(q,w) ∈ F} denote the words that P
accepts when started in state q ∈ Q.
Showthatiff isaDFA-homomorphismasabove,thenL(P,q)=L(P′,f(q))forallq∈Q.
(b) Hence, or otherwise, conclude that L(P) = L(P′) if there exists a DFA-homomorphism from P to P′, where L(P) denotes the language of P.
Solution of Exercise 3
(a) Weprovethatforallq∈Qandw∈Σ∗ wehave
w ∈ L(P,q) if and only if
We proceed by induction on the length of w. Base case. If w = ε, then we have
w ∈ L(P′,f(q)). (⋆)
(Definition of L )
ε ∈ L (P, q)
iff δ(q, ε) ∈ F
This proves the base case.
w ∈ L (P, q)
iff δ(q, w) ∈ F
(Definition of L )
iff f (q) ∈ F ′
(Definition of δ) (Because f is a DFA-homomorphism)
iff δ′(f(q),ε) ∈ F′
iff ε∈L(P′,f(q)) (DefinitionofL)
(Definition of δ′)
Step case. Our induction hypothesis (IH) is:
Forallv∈Σ∗ with|v|≤k−1,thestatementin(⋆)holds.
Here k is some arbitrary but fixed natural number. Weshowthatforallw∈Σ∗ with|w|=k,(⋆)holdsaswell.
Proof. Leta∈Σandv∈Σ∗ besuchthatw=av.Then|v|≤k−1.Thenwehave
iff δ(q,av)∈F
iff δ(δ(q, a), v) ∈ F
iff v ∈ L (P, δ(q, a))
iff v∈L(P′,f(δ(q,a))) iff v ∈ L(P′,δ′(f(q),a))
(Definition of δ) (Definition of L ) (BytheIH,because|v|≤k−1) (Because f is a DFA-homomorphism)
iff δ′(δ′(f(q),a),v) ∈ F′
(Definition of L)
iff δ′(f(q),av) ∈ F′
(Definition of δ′)
iff δ′(f(q),w) ∈ F′ (Because w = av)
iff w∈L(P′,f(q)) (DefinitionofL) This completes the proof of the step case.
(Wehavew=av)
Computer Science Tutoring
(b) It follows immediately from the definition that L(P ) = L (P, q0). Therefore we have:
L(P) = L(P,q0)
= L(P′,f(q0)) (By (a)) = L(P′,q0′ ) (f(q0) = q0′ because f is a DFA-homomorphism) = L(P′).
Exercise 4 PDAs with Finite Stack (10 credits)
In a pushdown automaton, there is no limit on the size of the stack. In this exercise, we demonstrate that this is essential, as PDAs with bounded stack size only accept regular languages. This is made formal in the following definition.
Definition. Let P = (Q,Σ,Γ,δ,q0,Z0,F) be a PDA and let w ∈ Σ∗ be a string. For a given a natural number n ∈ N, we say that P accepts w with stack bound n if there is a sequence
(p0,w0,γ0),…,(pk,wk,γk)
of IDs such that:
(B1) every transition is legal, i.e. (pi, wi, γi) ⊢P (pi+1, wi+1, γi+1) for all 0 ≤ i < k; (B2) The stack never contains more than n symbols, i.e. |γi| ≤ n for all 0 ≤ i ≤ k (B3) The sequence starts with the initial ID, i.e. p0 = q0, w0 = w, and γ0 = Z0 (B4) The string is accepted by final state, i.e. wk = ε, qk ∈ F .
Forn∈N,wewriteBn(P)={w∈Σ∗ |P acceptswwithstackboundn}andsaythatalanguage L is a bounded stack language if there is a PDA P and n ∈ N such that L = Bn(P).
It is easy to see (and you don’t need to prove that) that every language accepted by a DFA is also accepted with stack bound 1: from the DFA for the language, we construct a PDA that never modifies the stack. The converse is more interesting, and the subject of this exercise: show that every bounded stack language is regular.
Solution of Exercise 4
Let L be a bounded stack language. In order to show that L is regular, we construct an NFA A = (Q′,Σ,δ′,q0′ ,F′) with language L.
Since L is assumed to be a bounded stack language, there exists a PDA P = (Q,Σ,Γ,δ,q0,Z0,F) and a natural number n ∈ N such that L = Bn(P). Let
Q′ ={(q,γ)|q∈Q,γ∈Γ∗,|γ|≤n}. Define the transition map δ′ by
δ′((q,γ),a) = {(q′,γ′) ∈ Q′ | (q,a,γ) ⊢P (q′,ε,γ′)}. Furthermore, we set q0′ = (q0,Z0) and F = {(q,γ) ∈ Q′ | q ∈ F}.
Suppose w ∈ Bn(P). Then there is a sequence of IDs that satisfies the conditions stated in the question. Note that these are such that by definition this implies that (pi+1, γi+1) ∈ δ′((pi, γi), a), where wi = awi′. But this implies that (pk,γk) ∈ δ′((p0,γ0),w). By assumption pk ∈ F, therefore (pk,γk) ∈ F′ and hence w ∈ L(A).
Conversely, suppose w ∈ L(A). Then there is an element (p, γ) ∈ δ′(q0, Z0) such that (p, γ) ∈ F ′. But this is simply repeated application of δ′. If we write w = a0a1 · · · ak−1, then we have (pi, γi) ∈ Q′
such that (pi+1, γi+1) ∈ δ′((pi, γi), ai), hence by definition of δ′ (pi, wi, γi) ⊢P (pi+1, wi+1, γi+1), where wi = aiai+1 · · · ak−1. This gives rise to a sequence of IDs satisfying (B1) to (B4) from the definition above whose last element is (p, ε, γ) (where (p, γ) ∈ F ′ as noted above) . Since (p, γ) ∈ F ′ we must have p ∈ F, and hence w ∈ Bn(P).
Exercise 5 Buffalo (3 + 4 + 3 credits) This question is based on the fun fact that the English word “buffalo” has three meanings:
• A proper noun (always capitalised as “Buffalo”), referring to a location in New York • A transitive verb, meaning “to bully”
• A common noun, meaning the animal, bison (or a group of such animals)
Because of its versatility, the following string is a grammatically correct English sentence: “Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo.”
It means: “New York bison, that other New York bison bully, also bully New York bison.”
In the following, we are considering a context free grammar G over the alphabet {a, b} that derives the above sentence by writing “Buffalo” for a and “buffalo” for b, initially without paying attention to the fact that the first word of a sentence is capitalised, which you are asked to remedy in part (c).
Formally, the grammar G is given by the following productions:
S → NV N N → NNV N → ab N→b
(a) Construct parse trees for the following string:
(ii) ababbabbbab
(iii) ababbbab
(b) Is the above grammar ambiguous? Either prove that every w ∈ L(G) only has one parse tree, or demonstrate that G is ambiguous by giving a string w ∈ L(G) and two different parse trees with yield w.
(c) Define a grammar G′ such that L(G′) = {aw | aw ∈ L(G) or bw ∈ L(G)}. That is, L(G′) arises from L(G) by replacing the first letter of a string in L(G) by the letter ’a’. You are just required to state the grammar, and a proof of L(G) = L(G′) is not required.
Solution of Exercise 5
(a) (i) For bbab,
(ii) For ababbabbbab,
S NVN b b ab
(iii) For ababbbab,
ab ab b ab b b ab
ab ab b b ab
(b) There are more than one possible solutions. A possible solution is: we can construct bbbbb in the following two ways,
SS NVNNVN NNV NNV bbbbb bbbbb
(c) We introduce a new symbol which mimics N on the left-most position to guarantee an upper-case Buffalo.
N → NNV | ab | b
Nu →NuNV |ab|a V→b
Code Help, Add WeChat: cstutorcs