The Australian National University Semester 1, 2022 Research School of Computer Science Tutorial 4
Theory of Computation
This tutorial sheet contains way more exercises that you will be able to solve or discuss in the tutorial.
Exercise 1 Non-Deterministic Context Free Languages
Copyright By PowCoder代写 加微信 powcoder
We investigate the relationship between unambiguous grammars, and languages that are accepted by a deterministic PDA. Let
LwwR = {wwR : w ∈ {0,1}∗}
where wR is the reversal of the string w. (The language LwwR is the set of all even length palindromes.)
1. Where is the key difficulty when trying to construct a deterministic PDA that accepts precisely LwwR ? (We can prove that this language cannot be recognised by a deterministic PDA, but this is very hard, and you’re not asked to do this.)
Solution. The DPDA needs to distinguish the strings 0n110n and 0n110n+1, accepting the first, and rejecting the second. For the DPDA to be able to check that there are the same number of zeros before and after the ones, it needs to drain the stack of zeros, popping and matching as it does (as the state machine has only finite memory, and the DPDA cannot access symbols lower on the stack without destroying the ones on top.) Since the PDA cannot predict the number of characters ahead of time to test the strings 0n110n (or 0n110n+1), the DPDA must has forgotten how many zeros it has read. Which means if we feed it the string 0n110n0m110m, (which is in the language if and only if n = m), the DPDA can’t tell if n = m, as it has forgotten what n was. (Note that a PDA can just “guess” where the middle of the string is, and start popping from there.)
2. Construct an unambiguous grammar for LwwR . Prove your grammar is unambiguous, and that it really does generate the language.
Solution. We choose the grammar G given by the productions S →0S0|1S1|ε.
Note that grammar can only produce even length strings, as each production rule either adds 0 or 2 terminal symbols.
To see that G creates only even-length palindromes, we show that S ⇒∗ α implies that α ∈ {wwR | w∈Σ∗}∪{wSwR |w∈Σ∗}.
If the derivation S ⇒∗ α is of length 0, then α = S and the claim is clear. If the derivation is of length n + 1, we have that
S ⇒n β ⇒ α.
• β ∈ {wwR | w ∈ Σ∗} which is impossible, as strings of this form do not contain variables that
By induction hypothesis, it is either that: can be re-written in a next step; or
• β = wSwR for some w ∈ Σ∗. Applying the production rules, we have three sub-cases α = w0S0wR, α = w1S1wR or α = wwR, and all three cases have the required form.
TO see that G creates all even-length palindromes, we show by induction on w ∈ Σ∗ that S ⇒ wSwR, and the result follows by applying the production S → ε.
For the base case w = ε, we have that S ⇒∗ S using a derivation of length 0. For the step case, assume that S ⇒∗ wSwR. Then, using the productions S → 0S0 and S → 0S1, we also have that S ⇒∗ w0S0wR = (w0)S(w0)R and S ⇒ w1s1wR = (w1)S(w1)R as required.
To see that the grammar is unambiguous, we show that any two different derivations generate differenteven-lengthpalindromes.SoletS⇒α1 ⇒α2···⇒αn =xandS⇒β1 ⇒β2···⇒βm = y be two different derivations, with x, y ∈ Σ∗.
Wehavealreadyseenabovethateachαi andβj isoftheformwSwR fori