The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Selected Tutorial Solutions, Week 9
73. (a) {w|wbeginswitha1andendswitha0}: 1(0∪1)∗0 (b) {w | w contains the substring 0101}: (0 ∪ 1)∗0101(0 ∪ 1)∗
74.
(c) {w|whaslengthatleast3anditsthirdsymbolis0}: (0∪1)(0∪1)0(0∪1)∗
(d) {w|thelengthofwisatmost5}: (ε∪0∪1)(ε∪0∪1)(ε∪0∪1)(ε∪0∪1)(ε∪0∪1)
(e) {w | w is any string except 11 and 111}: ε ∪ 1 ∪ 11111∗ ∪ (0 ∪ 1)∗0(0 ∪ 1)∗ (f) {w|everyoddpositionofwisa1}: (1(0∪1))∗(ε∪1)
(g) {w | w contains at least two 0s and at most one 1}: 0∗(00 ∪ 001 ∪ 010 ∪ 100)0∗ (h) {ε,0}: ε∪0
(i) The empty set: ∅
(j) All strings except the empty string: (0 ∪ 1)(0 ∪ 1)∗
If A is regular then suffix(A) is regular. Namely, let D = (Q,Σ,δ,q0,F) be a DFA for A. Assume every state in Q is reachable from q0. Then we can turn D into an NFA N for suffix(A) by adding a new state q−1 which becomes the NFA’s start state. For each state q ∈ Q, we add an epsilon transition from q−1 to q.
That is, we define N to be (Q∪{q−1},Σ,δ′,q−1,F), with transition function
′ {δ(q,x)} forq∈Qandx∈Σ δ(q,x)= Q forq=q−1 andx=ε ∅ forq̸=q−1 andx=ε
The restriction we assumed, that all of D’s states are reachable, is not a severe one. It is easy to identify unreachable states and eliminate them (which of course does not change the language of the DFA). To see why we need to eliminate unreachable states before generating N in the suggested way, consider what happens to this DFA for {ε}: ({q0, q1, q2}, {a}, δ, q0, {q0}), where δ(q0, a) = δ(q1, a) = q1 and δ(q2, a) = q0.
75.
(a) Here is an NFA for (ba∗a)∗:
(b) Here is an equivalent DFA, obtained using the subset construction:
1 b 2 b
∅
(c) It is easy to get a DFA for the complement:
a
b
1,2 a
a a,b
b
12
a
a
1 b 2 b
∅
a
b
1,2 a
a a,b
(d) It would be problematic to do the “complement trick” on the NFA, as it is only guaranteed to work on DFAs. We would get the following, which accepts, for example, baa:
b
12
a
a
(e) Starting from the DFA that we found in (c), we make sure that we have just one accept
state:
a
b
1 b 2 abε
1,2 a
a∪b∅εx Let us first remove the state labeled 1,2:
b
1 2aa∗b
abε a∪b∅εx
Now we can remove state 2: 1
b(aa∗b)∗ a∪b∅εx
Finally, eliminating the state labelled ∅, we are left with:
a ∪ b(aa∗b)∗b
b(aa∗b)∗ ∪ a(a ∪ b)∗ ∪ b(aa∗b)∗b(a ∪ b)∗
x
1
The resulting regular expression can be read from that diagram.
76. (a)WeshowthatA={0n1n2n |n≥0}isnotregular. Assumeitis,andletpbethe pumping length. Consider s = 0p1p2p ∈ A. Since |s| ≥ p, by the pumping lemma, s canbewrittens=xyz,sothaty̸=ε,|xy|≤p,andxyiz∈Aforalli≥0. Butsince |xy| ≤ p, y must contain 0s only. Hence xz ̸∈ A. Thus we have a contradiction, and we conclude that A is not regular.
(b) We use the pumping lemma to show that B is not regular. Assume that it were. Let p be the pumping length, and consider ap+1bap. This string is in B and of length 2p + 2. By the pumping lemma, there are strings x, y, and z such that ap+1bap = xyz, with y ̸= ε, |xy| ≤ p, and xyiz ∈ B for all i ∈ N. By the first two conditions, y must be a non-empty string consisting of as only. But then, pumping down, we get xz, in which the number of as on the left no longer is strictly larger than the number of as on the right. Hence we have a contradiction, and we conclude that B is not regular.
(c) We want to show that C = {w ∈ {a, b}∗ | w is not a palindrome} is not regular. But since regular languages are closed under complement, it will suffice to show that Cc = {w ∈ {a,b}∗ | w is a palindrome} is not regular. Assume that Cc is regular, and let p be the pumping length. Consider apbap ∈ Cc. Since |s| ≥ p, by the pumping lemma, scanbewrittens=xyz,sothaty̸=ε,|xy|≤p,andxyiz∈Cc foralli≥0. But since |xy| ≤ p, y must contain as only. Hence xz ̸∈ Cc. We have a contradiction, and we conclude that Cc is not regular. Now if C was regular, Cc would be regular too. Hence C cannot be regular.
77. Here are the context-free grammars:
(a) {w | w starts and ends with the same symbol}:
S→0T0|1T1|0|1 T → 0T|1T|ε
(b) {w | the length of w is odd}:
S → 0|1|00S|01S|10S|11S
(c) {w | the length of w is odd and its middle symbol is 0}:
S → 0|0S0|0S1|1S0|1S1
(d) {w | w is a palindrome}:
S → 0S0|1S1|0|1|ε
78. Here is a context-free grammar for {aibaj | i > j ≥ 0}:
S→AB A→a|aA B → b|aBa
79. The class of context-free languages is closed under the regular operations: union, concatena- tion, and Kleene star.
Let G1 and G2 be context-free grammars generating L1 and L2, respectively. First, if necessary, rename variables in G2 so that the two grammars have no variables in common. Let the start
variables of G1 and G2 be S1 and S2, respectively. Then we get a context-free grammar for L1 ∪ L2 by keeping the rules from G1 and G2, adding
S → S1 S → S2
where S is a fresh variable, and making S the new start variable.
We can do exactly the same sort of thing for L1 ◦ L2. The only difference is that we now just
add one rule:
again making (the fresh) S the new start variable.
S → S1 S2
Let G be a context-free grammar for L and let S be fresh. If we add two rules to those from
G:
S→ε
S → SS′
where S′ is G’s start variable, then we have a context-free grammar for L∗ (it has the fresh S as its start variable).
80. Here are some sentences generated from the grammar:
(a) A dog runs
(b) A dog likes a bone
(c) The quick dog chases the lazy cat (d) A lazy bone chases a cat
(e) The lazy cat hides
(f) The lazy cat hides a bone
The grammar is concerned with the structure of well-formed sentences; it says nothing about meaning. A sentence such as “a lazy bone chases a cat” is syntactically correct—its structure makes sense; it could even be semantically correct, for example, “lazy bone” may be a deroga- tory characterisation of some person. But in general there is no guarantee that a well-formed sentence carries meaning.
81. We can easily extend the grammar so that a sentence may end with an optional adverbial
modifier:
S →NPVPPP .
PP → ε
PP → quietly PP → all day
.