2D1371 Automata Theory

2D1371 Automata Theory
Examination Problems Dilian Gurov

with selected solutions KTH CSC
28 May 2007 08-790 81 98
1. Convert the nondeterministic automaton given below to an equivalent deterministic one using the
subset construction (textbook Lecture 6). Omit inaccessible states. Draw the graph of the resulting
DFA.
a b
→ q0 {q2 } ∅
→ q1 F {q0 , q2 } ∅
q2 F ∅ {q1 , q2 }
Solution: (as a table)
a b
→ {q0 , q1 } F {q0 , q2 } ∅
{q0 , q2 } F {q2 } {q1 , q2 }
{q1 , q2 } F {q0 , q2 } {q1 , q2 }
{q2 } F ∅ {q1 , q2 }
∅ ∅ ∅
2. For the deterministic automaton given below, apply the minimization algorithm of textbook Lecture 14
to compute the equvalence classes of the collapsing relation ≈ defined in textbook Lecture 13.
a b
→ q0 q2 q0
q1 q0 q2
q2 F q4 q3
q3 q0 q4
q4 F q4 q1
(a) Show clearly the computation steps (use tables).

(b) List the computed equivalence classes.
Solution: These are {q0 }, {q1 , q3 } and {q2 , q4 }.
(c) Apply the quotient construction of textbook Lecture 13 to derive the minimized automaton.
Draw its graph.
Solution: (as a table)
a b
→ {q0 } {q2 , q4 } {q0 }
{q1 , q3 } {q0 } {q2 , q4 }
{q2 , q4 } F {q2 , q4 } {q1 , q3 }
3. A context–free grammar G = (N, Σ, P, S) is called strongly right–linear (or SRLG for short) if all its
productions are of shape A → aB or A → . Let us call a SRLG deterministic if for each non–terminal
A ∈ N and terminal a ∈ Σ there is exactly one production of shape A → aB (while productions of
shape A → are optional).
Define a complement construction on deterministic SRLGs. That is, for deterministic SRLGs G define
the complement G as a deterministic SRLG for which you show that L(G) = L(G).
Solution: Recall that there is a one–to–one corespondence beween DFAs and SRLGs, and recall the
complement construction on DFAs. Let G = (N, Σ, P, S) be a deterministic SRLG. We define the
def def
complement of G as the deterministic SRLG G = (N, Σ, P , S) where P = {A → aB | A → aB ∈ P } ∪
{A → | A → 6∈ P } is the set of productions of G. Then,
+
x ∈ L(G) ⇔ S →G x {Def. L(G)}
n o
+
⇔ ∃!A ∈ N. (S →G xA ∧ A → ∈ P ) G a deterministic SRLG
n o
⇔ ∃!A ∈ N. (S →+
G xA ∧ A → 6∈ P ) Def. G
⇔ not S →+G x {G a deterministic SRLG}
⇔ x 6∈ L(G) {Def. L(G)}
⇔ x ∈ L(G) {Set theory}
and therefore L(G) = L(G).
4. Recall the Chomsky–Schützenberger Theorem (textbook Supplementary Lecture G). Show how this
theorem applies to the context–free language
A = {x ∈ {a, b}∗ | ]a(x) = ]b(x)}

def
over the alphabet Σ = {a, b}, by identifying:
• a suitable natural number n,

• a regular language R over the alphabet Σn of the n–th balanced parentheses language, and
• a homomorphism h : Σn → Σ∗ ,
for which you argue that A = h(PARENn ∩ R) holds.

Solution: Recalling that A is generated by the grammar S → | aSb | bSa | SS it is easy to see that
A = h(PARENn ∩ R) holds for n = 2, R = (Σn )∗ and h defined by h([1 ) = a, h(]1 ) = b, h([2 ) = b and
h(]2 ) = a.
5. Consider the language:

A = {am bn | m ≤ n}
(a) Use the Pumping Lemma for regular languages (as a game with a Deamon) to prove that A is
not regular.
(b) Refer to the closure properties of context–free languages to argue that A is context–free. That
is, represent A as the result of some operation(s) on context–free languages (which we already
know to be context–free) under which CFLs are closed.
def def
Solution: A = B · C for B = {am bm | m ≥ 0} and C = {bn | n ≥ 0}, both of which we know to
be context–free, and we know CFLs to be closed under language concatenation.
(c) Give a context–free grammar G generating A.
Solution: One possibility is the grammar S → | aSb | Sb.
(d) Prove your grammar correct. You are allowed to reuse results proved in class.
(e) Construct an NPDA accepting A − {} on empty stack. Explain your choice of productions.
Solution: One solution is a NPDA with one control state q and productions:
a
hq, Si ,→ hq, SAi
a
hq, Si ,→ hq, Ai
b
hq, Ai ,→ hq, Ai
b
hq, Ai ,→ hq, i
The automaton uses the first production for reading all initial a’s but the last, then guesses the
last a and uses the second production to get rid of the S at the top of the stack. The stack now
has as many A’s as the a’s read so far. The automaton guesses the number of b’s in excess of a’s
in the string, and uses the third production that many times. The stack now has as many A’s as
there are remaining (unread) b’s. The automaton uses production four to empty the stack upon
reading the whole string.
6. Let M range over deterministic finite automata (DFA).
(a) Describe a uniform, injective encoding of DFAs into strings over the alphabet {0, 1}.
Solution: Such an encoding was discussed in class.
(b) Let M̂ ∈ {0, 1}∗ denote the encoding of M . As we know from Cantor’s theorem, the set
n o
A = M̂ ∈ {0, 1}∗ | M̂ 6∈ L(M )
def
is not regular (since it is the inverted diagonal set). Argue, however, that A is recursive by giving
a (reasonably detailed) description of a total Turing machine accepting A.
Solution: (Sketch) The Turing machine T starts by modifying the input M̂ to M̂ ]qˆ0 ]M̂ where
q0 is the initial state of M . The added part qˆ0 ]M̂ represents the initial configuration of M (where
a configuration of a DFA is understood as a pair consisting of a state and the suffix of the input
string that remains to be read). T continues by simulating M on M̂ , by iteratively computing
and updating the current state of M until the input string M̂ has been completely consumed.
This is achieved by reading (and consuming) the next symbol of the input string M̂ of M , and
looking up from M̂ (always available in the first segment of the tape) the next state of M . Finally,
T checks whether the state in the final configuration of M is an accepting state, and rejects resp.
accepts accordingly. Thus, T is a total Turing machine accepting language A.
7. Consider the language n o

def
VTP = M̂ ]x̂]q̂ | M run on x visits q twice
where ”M visits q” means that Turing machine M is at a configuration with control state q. Show
that language VTP is not recursive by reducing from undecidability of the Membership Problem.
That is, given a total Turing machine MVTP deciding VTP, construct a total Turing machine MMP
deciding MP, where: n o
def
MP = M̂ ]x̂ | M accepts x
Solution: Assume there is a total Turing machine MVTP accepting VTP. Then we can construct a
Turing machine MMP as follows.
On input M̂ ]x̂, MMP modifies the input to M d0 ]x̂]v̂ where M 0 is like M but is modified as follows: two
new control states u and v are added, the latter of which is made the new accept state of M 0 , and the
transition function δ of M is extended to δ 0 so that δ 0 (t, a) = (u, \, R) and δ 0 (u, a) = (t, a, L) for all a
in the input alphabet of M , and δ 0 (t, \) = (v, \, R), where t is the original accept state of M and \ is a
tape symbol of MMP not used elsewhere. Notice that M 0 visits state t twice on input x exactly when
M visits t on x, that is, when M accepts x. MMP then continues as MVTP .
Then:
d0 ]x̂]v̂
MMP accepts M̂ ]x̂ ⇔ MVTP accepts M
0
⇔ M run on x visits v twice
⇔ M accepts x
Since MVTP is total, so is MMP , and so MMP decides MP which we know to be undecidable. Hence
there is no total Turing machine MVTP accepting VTP.

2D1371 Automata Theory

Uploaded by

Copyright:

Available Formats

2D1371 Automata Theory

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

2D1371 Automata Theory

Uploaded by

Copyright:

Available Formats

2D1371 Automata Theory

Examination Problems Dilian Gurov

Solution: (as a table)

(a) Show clearly the computation steps (use tables).

and therefore L(G) = L(G).

A = {x ∈ {a, b}∗ | ]a(x) = ]b(x)}

over the alphabet Σ = {a, b}, by identifying:

• a suitable natural number n,

for which you argue that A = h(PARENn ∩ R) holds.

5. Consider the language:

6. Let M range over deterministic finite automata (DFA).

7. Consider the language n o

You might also like