/Users/billy/gits/moc-2021/problem-sets/ps09.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 9
27 September – 1 October 2021
Content: regular expressions, NFAs, context-free grammars, the pumping lemma.
P9.1 Give regular expressions for the following languages over the alphabet Σ = {0, 1}.
(i) {w | w has length at least 3 and its third symbol is 0}
(ii) {w | every odd position of w is a 1}
(iii) {w | w contains at least two 0s and at most one 1}
(iv) {ǫ, 0}
(v) The empty set
Bonus: Draw minimal NFAs for these languages, and those from T9.1
P9.2 String s is a suffix of string t iff there exists some string u (possibly empty) such that t = us.
For any language L we can define the set of suffixes of strings in L:
suffix (L) = {x | x is a suffix of some y ∈ L}
Let A be any regular language. Show that suffix (A) is a regular language. Hint: Think about
how a DFA for A can be transformed to recognise suffix (A).
P9.3 In general it is difficult, given a regular expression, to find a regular expression for its com-
plement. However, it can be done, and you have been given all the necessary tricks and
algorithms. This question asks you to go through the required steps for a particular example.
Consider the regular language (ba∗a)∗. Assuming the alphabet is Σ = {a, b}, we want to find
a regular expression for its complement, that is, for
L = {w ∈ {a, b}∗ | w is not in (ba∗a)∗}
To complete this task, go through the following steps.
(a) Construct an NFA for (ba∗a)∗. Two states suffice.
(b) Turn the NFA into a DFA using the subset construction method.
(c) Do the “complement trick” to get a DFA D for L.
(d) Reflect on the result: Wouldn’t it have been better/easier to apply the “complement
trick” directly to the NFA?
(e) Turn DFA D into a regular expression for L using the NFA-to-regular-expression trans-
lation shown in the lecture on regular expressions (not examinable).
P9.4 A palindrome is a string that reads the same forwards and backwards. Use the pumping
lemma for regular languages and/or closure results to prove that the following languages are
not regular:
(a) B = {aibaj | i > j ≥ 0}
(b) C = {w ∈ {a, b}∗ | w is not a palindrome}
(c) D = {www | w ∈ {a, b}∗}
P9.5 Give context-free grammars for the following languages. Assume the alphabet is Σ = {0, 1}.
(i) {w | w starts and ends with the same symbol}
(ii) {w | the length of w is odd}
P9.6 Construct a context-free grammar for the language {aibaj | i > j ≥ 0}.
P9.7 Show that the class of context-free languages is closed under the regular operations: union,
concatenation, and Kleene star. Hint: Show how context-free grammars for A and B can
be manipulated to produce context-free grammars for A ∪ B, AB, and A∗. Careful: The
variables used in the grammars for A and in B could overlap.
P9.8 If we consider English words the “symbols” (or primitives) of English, we can use a context-
free grammar to try to capture certain classes of sentences and phrases. For example, we
can consider articles (A), nouns (N), adjectives (Q), intransitive verbs (IV ), transitive verbs
(TV ), noun phrases (NP ), verb phrases (V P ), and sentences (S). List 5–10 sentences gen-
erated by this grammar:
S → NP VP
A → a
A → the
NP → A N
NP → A Q N
N → bone
N → cat
N → dog
Q → lazy
Q → quick
VP → IV
VP → TV NP
IV → hides
IV → runs
IV → sleeps
TV → chases
TV → hides
TV → likes
Are they all meaningful? Discuss “well-formed” versus “meaningful”.
P9.9 How would you change the grammar from the previous question so that “adverbial modifiers”
such as “angrily” or “happily” can be used? For example, we would like to be able to generate
sentences like “the dog barks constantly” and “the black cat sleeps quietly”.
P9.10 Consider this context-free grammar G with start symbol S:
S → a b a | a b A | b B
A → b | b A | a B
B → a A | a B
Draw an NFA which recognises L(G). Hint: The grammar is a regular grammar; you may
want to use the labels S, A, and B for three of the NFA’s states.
P9.11 Consider the context-free grammar G with rules
S → a b | a S b | S S
Use structural induction to show that no string w ∈ L(G) starts with abb.
P9.12 Consider the context-free grammar ({S}, {a, b}, R, S) with rules R:
S → a | b | S S
Show that the grammar is ambiguous; then find an equivalent unambiguous grammar.
P9.13 Give a context-free grammar for the language recognised by this DFA:
1 2
34
a
b ba
a
ba, b