The plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 10
14–16 October 2020
The Week 10 exercises concentrate on context-free languages and grammars. Most exercises have been carried over from before the break.
A reminder that supporting reading is available through “Readings Online” on Canvas (the book chapter by Sudkamp). The teaching-free break will hopefully give you an opportunity to catch up on the material on automata, grammars, and formal languages, and to complete the last assessed worksheet. You should then have all the background knowledge needed to complete Assignment 2, well before the deadline.
The exercises
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 →TVNP
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. 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. 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
87. (Drill.) Give a context-free grammar for {aibjck | i = j ∨ j = k where i,j,k ≥ 0}. Is your grammar ambiguous? Why or why not?
88. (Drill.) Consider the context-free grammar G = ({S, A, B}, {a, b}, R, S) with rules R:
S→ABA A→aA|ε B→bB|ε
(a) Show that G is ambiguous.
(b) The language generated by G is regular; give a regular expression for L(G).
(c) Give an unambiguous context-free grammar, equivalent to G. Hint: As an intermediate step, you may want to build a DFA for L(G).
89. Construct a push-down automaton which recognises the language from Exercise 78, that is, {aibaj |i>j≥0}.