School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 9
30 September to 2 October 2020
The exercises
73. Give regular expressions for the following languages over the alphabet Σ = {0, 1}.
(a) {w|wbeginswitha1andendswitha0}
(b) {w | w contains the substring 0101} (so w = x0101y for some strings x and y)
(c) {w | w has length at least 3 and its third symbol is 0} (d) {w|thelengthofwisatmost5}
(e) {w | w is any string except 11 and 111} (f) {w | every odd position of w is a 1}
(g) {w | w contains at least two 0s and at most one 1} (h) {ε,0}
(i) The empty set
(j) All strings except the empty string
74. 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).
75. 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}∗ |wisnotin(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).
76. 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) A={0n1n2n |n≥0} (b) B={aibaj |i>j≥0}
(c) C = {w ∈ {a, b}∗ | w is not a palindrome}
77. Give context-free grammars for the following languages. Assume the alphabet is Σ = {0, 1}.
(a) {w | w starts and ends with the same symbol} (b) {w | the length of w is odd}
(c) {w | the length of w is odd and its middle symbol is 0} (d) {w | w is a palindrome}
78. Construct a context-free grammar for the language {aibaj | i > j ≥ 0}.
79. 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.
80. 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 (VP), and sentences (S). List 5–10 sentences gen- erated by this grammar:
S → NPVP A →a
A → the
NP →AN NP → AQN 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”.
81. 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”.
82. Consider this context-free grammar G with start symbol S:
S → aba|abA|bB A → b|bA|aB
B → aA|aB
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.
83. Consider the context-free grammar G with rules
S → ab |aSb|SS
Use structural induction to show that no string w ∈ L(G) starts with abb.
84. (Drill.) Consider the context-free grammar ({S}, {a, b}, R, S) with rules R:
S → a|b|SS
Show that the grammar is ambiguous; then find an equivalent unambiguous grammar.
85. (Drill.) Consider the context-free grammar ({A, B, T }, {a, b}, R, T ) with rules R:
T→A|B
A → ab|aAb B → ε|abB
Show that the grammar is ambiguous; then find an equivalent unambiguous grammar. 86. (Drill.) Give a context-free grammar for the language recognised by this DFA:
a
12
a
bab
a,b 4 3 b