CS 154 Introduction to Automata and Complexity Theory Handout 16

Winter 1996  R. van Glabbeek  February 21, 1996

Midterm Exam—Solutions

Problem 1 (25 points) Construct a 2SM (Stack machine with control over two stacks) the recognizes the language

{x#x : x ∈ (a ∪ b)^{∗}}

Figure 1: 2SM recognizing the given language

Problem 2 (20 points) Does the given string belong to the given regular set

Yes 01110111 ∈ (1^{∗}01)^{∗}(11 ∪ 0^{∗})

No 11100111 ∈ ((1^{∗}0)^{∗} ∪ 0^{∗}11)^{∗}

No 011100101 ∈ 01^{∗}10^{∗}(11^{∗}0)^{∗}

Yes 1000011 ∈ (10^{∗} ∪ 11)^{∗}(0^{∗}1)^{∗} Problem 3 (35 points) Are the following languages regular? (Prove your answer.)

1. {0^{n} : n is a multiple of 8 }

Yes, (00000000)^{∗} is a regular expression for this language.

2. {w : w ∈ (0 ∪ 1)^{∗} and w contains more 0’s than 1’s }

No, with pumping lemma: Let N be given. Choose z = 1^{N}0^{N+1}. If z = uvw with |v| > 0 and |uv| ≤ N, then v = |1^{k}| with 1 ≤ k ≤ N, and uv^{2}w is not in the language.

3. {w : w ∈ (0 ∪ 1)^{∗} and w contains no substring of the form xxx with |x| ≥ 1}. Answer this question under each of the following assumptions:

• There exists an infinite string w, such that w contains no substring of the form xxx, with |x| ≥ 1.

• There exists no such string.

You don’t have to decide which of these assumptions is valid.

Suppose there is an infinite string as mentioned above. Then the language is not regular, as can be shown with the pumping lemma. Let N be given. Choose a string z in the language with |z| ≥ N. Such a string exists: just take a prefix of the infinite string w. Let z = uvy with |v| > 0, then uv^{3}y is not in the language.

Suppose there is no infinite string as above. Then the language must be finite, and hence regular. For suppose it is infinite: consider the infinite tree (as in exercise 0.6-29 of FB) whose nodes are the strings of the language, with Λ as root and x as parent of xa for a ∈ {0, 1}. This tree is finite-branching and therefore, by König’s lemma, has an infinite branch. This infinite branch consist of a chain of strings, each one extending its parent by one letter, that do not contain substrings of the form xxx with |x| ≥ 1. This gives rise to an infinite string which does not contain such substrings, contradicting the assumption. Therefore the language must be finite. Finally note that any finite language is regular.

Problem 4 (30 points)

1. Minimize the DFA in Figure 2 by determining E_{0}, E_{1}, E_{2}, … until a fixpoint, as done in Section 4.7.1.

2. Extract the regular expression corresponding to the constructed DFA. The initial state in Figure 2 is Q0, the final states are Q6 and Q7.

Figure 2: DFA to be minimized (Please try to be neat with your diagrams)

1.  \begin{aligned}E_{0} & = & \{\{Q0, Q1, Q2, Q3, Q4, Q5\}, \{Q6, Q7\}\} \\ E_{1} & = & \{\{Q0, Q1, Q2, Q3\}, \{Q4, Q5\}, \{Q6, Q7\}\} \\ E_{2} & = & \{\{Q0, Q1\}, \{Q2, Q3\}, \{Q4, Q5\}, \{Q6, Q7\}\} \\ E_{3} & = & E_{2} \end{aligned}

Figure 3: Minimized DFA

The final state is drawn with two circles.

2. A regular expression corresponding to the automata is: 1^{∗}01^{∗}01^{∗}(01^{∗}01^{∗})^{∗}01^{∗} Problem 5 (45 points) Consider the following CFG:

\begin{aligned}S & → & ABC \\ A & → & DE \\ B & → & F GH \\ B & → & b \\ C & → & cd \\ D & → & CD \\ D & → & Λ \\ E & → & Dc \\ F & → & dC \\ G & → & BH \\ H & → & ab \end{aligned}

1. Construct a parse tree for cdcdcdbababcd.

S A D C c d D Λ  E D Λ c  B F d  C c d G B b  H a b  H a b  C c d

2. Is the grammar ambiguous? Explain why, and construct an unambiguous CFG generating the same language. Yes, it’s ambiguous; here is another parse tree for the same string:

S A D Λ  E D C c d D Λ c  B F d  C c d G B b  H a b  H a b  C c d

An unambiguous CFG generating the same language is obtained by changing A → DE into A → E, or E → Dc into E → c (but not both).

3. Write cdcdcdbababcd as uvwxy such that |u| > 0, |vx| > 0, and for i ≥ 0 also uv^{i}wx^{i}y is in the language generated by the CFG.

\begin{matrix}cdc & dcd & b & abab & cd \\ u & v & w & x & y \end{matrix} (take subtrees sprouting from B in parse tree).

Problem 6 (30 points)

1. Give a context-free grammar generating the set of all strings of balanced parenthesis [ and ]. In such a string each “[” has a matching “]”, and pairs of matching parenthesis are properly nested.

\begin{matrix}S → Λ \\ S → [S]S \end{matrix}  or  \begin{matrix}S → Λ \\ S → SS \\ S → [S] \end{matrix}

2. Convert the context free grammar from 1. into Chomsky Normal Form.

S → Λ S → T T → T T T → BR R → T E B → [ E → ] R → ]

Problem 7 (20 points) Prove that {xxxw : x ∈ (0 ∪ 1)^{+}, w ∈ (0 ∪ 1)^{∗}} is not context free.

With pumping lemma and intersection:

Intersect with the regular language 10^{∗}10^{∗}10^{∗}. It suffices to prove that the resulting language L = {10^{n}10^{n}10^{n+m} | n, m ≥ 0} is not context-free, since CFL’s are closed under intersection with a regular language.

Let N be given. Choose z = 10^{N}10^{N}10^{N}. If z = uvwxy with |vx| > 0, and v or x contains a 1, take i = 0 and uv^{i}wx^{i}y has less than three 1’s and cannot be in L. In the remaining case v and x contain 0’s from at most two groups.

• If |v| = |x| and they take 0’s from the first two groups, pump up: uv^{2}wx^{2}y = 10^{n+|v|}10^{n+|v|}10^{n} ∉ L.

• In all other cases pump down: uwy ∉ L (either the first two groups of 0’s have a different length or the last group contains less 0’s then the other groups).

Problem 8 (15 points) Is the class of deterministic counter languages closed under intersection ? Prove your answer or provide a counterexample. A mere yes or no will get no points. No: The languages a^{n}b^{n}c^{∗} and a^{∗}b^{n}c^{n} are both DCLs (easy), but their intersection a^{n}b^{n}c^{n} is not context free (FB Example 5.22, p359), and hence not a DCL (as DCL ⊆ CF L).

Problem 9 (30 points)

A bisimulation between acceptors P = (α, Π, ω) and P′ = (α′, Π′, ω′) is given by a relation of representation satisfying conditions 1–12 below.

L(P) = L(P′) L(P) ⊆ L(P′) _{L}(P) = _{L}(P′) _{L}(P) ⊆ _{L}(P′)
1 x ↦^{α} C ⇒ (∃C′)[x ↦^{α′} C′ρC]  √  √  √
2 x ↦^{α} C ⇐ [x ↦^{α′} C′ρC]  √
3 [C′_{0}ρC_{0} ↦^{Π} C_{1}] ⇒ (∃C′_{1})[C′_{0} ↦^{Π′} C′_{1}ρC_{1}]  √  √  √  √
4 (∃C_{0})[C′_{0}ρC_{0} ↦^{Π} C_{1}] ⇐ [C′_{0} ↦^{Π′} C′_{1}ρC_{1}]  √
5 [C′_{0}ρC_{0} ↦^{ω} ACCEPT] ⇒ [C′_{0} ↦^{ω′} ACCEPT]  √  √  √  √
6 (∃C_{0})[C′_{0}ρC_{0} ↦^{ω} ACCEPT] ⇐ [C′_{0} ↦^{ω′} ACCEPT]  √
7 x ↦^{α′} C′ ⇒ (∃C)[x ↦^{α} Cρ^{−1}C′]  √  √
8 x ↦^{α′} C′ ⇐ [x ↦^{α} Cρ^{−1}C′]
9 [C_{0}ρ^{−1}C′_{0} ↦^{Π′} C′_{1}] ⇒ (∃C_{1})[C_{0} ↦^{Π} C_{1}ρ^{−1}C′_{1}] √ √
10 (∃C′_{0})[C_{0}ρ^{−1}C′_{0} ↦^{Π′} C′_{1}] ⇐ [C_{0} ↦^{Π} C_{1}ρ^{−1}C′_{1}]
11 [C_{0}ρ^{−1}C′_{0} ↦^{ω′} ACCEPT] ⇒ [C_{0} ↦^{ω} ACCEPT] √
12 (∃C′_{0})[C_{0}ρ^{−1}C′_{0} ↦^{ω′} ACCEPT] ⇐ [C_{0} ↦^{ω} ACCEPT]

The first 6 conditions say that ρ is a lockstep simulation of P by P′; the last 6 say that its converse relation (pp. 21 FB) ρ^{−1} is a lockstep simulation of P′ by P. Let L̃(P) be the language accepted by an acceptor P, according to the alternative definition of acceptance given in Footnote 5 in Section 1.9 of FB (pp. 101): programs accept if every sequence of legal transitions leads to acceptance. A usual, L(P) denotes the language accepted by P under the standard definition of acceptance: programs accept if some sequence of legal transitions leads to acceptance. In the course it has been shown that if there exists a relation ρ satisfying conditions 1–6, then L(P) = L(P′).

(a) Which of these conditions are needed to guarantee that L(P) ⊆ L(P′)? In one of the homeworks you had to show that the existence of a relation satisfying all 12 conditions implies L̃(P) = L̃(P′).

(b) Which of these conditions are actually needed to guarantee this?

(c) Which of these conditions are needed to guarantee that L̃(P) ⊆ L̃(P′)? Give your answers by placing checkmarks in the table above.