The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Selected Tutorial Solutions, Week 10
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:
82. Here is a suitable NFA:
83. Let w be a string in L(G), that is, w is derived from S. We will use structural induction to show a stronger statement than what was required; namely we show that, for every string w ∈ L(G), w starts with neither b nor abb. That is, if w is derived from S then it starts with neither b nor abb. (To express the property formally, we may write ∀w′ ∈ {a, b}∗(w ̸= bw′ ∧w ̸= abbw′).
There is one base case: If w = ab then w does not start b and it does not start with abb.
For the first recursive case, let w = aw′b, where w′ ∈ L(G). By the induction assumption, w′ starts with neither b nor abb. Hence, in this case, w does not start with b (because it starts with a), and it does not start with abb (because w′ does not start with b).
For the second recursive case, let w = w′w′′, with w′, w′′ ∈ L(G). By the induction assumption, w′ starts with neither b nor abb (similarly for w′′). Let’s do case analysis on the length of w′.
• |w′| = 0: If w′ = ε then w = w′′ which starts with neither b nor abb, by assumption.
• |w′| = 1: In this case we must have w′ = a since, by assumption, w′ does not start with b. But then w doesn’t start with b, and it doesn’t start with abb either, because w′′ does not start with b, by assumption.
• |w′| ≥ 2: In this case w′ must start with either aa or ab. That means w does not start with b. And w can only start with abb if w′ = ab and w′′ starts with b. But the latter is impossible, by assumption.
S →NPVPPP .
PP → ε
PP → quietly PP → all day
.
aba
S
bb
a
BA
a a
b
b
Hence in no case does w start with abb.
2
Hence in no case does w start with abb.
84. Too easy.
85. The grammar is ambiguous because ab can be derived from A and also from B. However, it is the only string that can be derived from both, so we can make this grammar unambiguous simply by making sure that ab cannot be derived from A, or more precisely, making sure that the set of strings that can be derived from A is {anbn | n > 1}. To do this, change the first rule for A like so:
T→A|B
A → aabb|aAb B → ε|abB
86. Here is a context-free grammar that will do the job (S is the start symbol):
S→ε|aA
A → aA|bB
B → ε|aA|bB
88. We are looking at the context-free grammar G:
S→ABA A→aA|ε B→bB|ε
(a) The grammar is ambiguous. For example, a has two different leftmost derivations: S⇒ABA⇒BA⇒A⇒aA⇒a
S⇒ABA⇒aABA⇒aBA⇒aA⇒a
(b) L(G) = a∗b∗a∗.
(c) To find an unambiguous equivalent context-free grammar it helps to build a DFA for a∗b∗a∗. (If this is too hard, we can always construct an NFA, which is easy, and then translate the NFA to a DFA using the subset construction method, which is also easy.) Below is the DFA we end up with. The states are named S, T, and U to suggest how they can be made to correspond to variables in a context-free grammar. The DFA translates easily to the grammar on the right. The resulting grammar is a so-called regular grammar, and it is easy to see that it is unambiguous—there is never a choice of rule to use.
a,b
STU∅ 89. HereisaPDAfor{aibaj |i>j≥0}:
aba
bab
S → ε|aS|bT T → ε|bT|aU U→ε|aU
a, ε → a a, a → ε b, a → ε
ε, ε → x 123
Note that the stack won’t be empty when this PDA halts; and that’s okay. 3