CS 154 Introduction to Automata and Complexity Theory Handout 6

Winter 1996  R. van Glabbeek  January 29

Solution Set 2

Problem 1

Graded by Stephen Wu and Kenneth Cheng.

Figure 1: UCM accepting strings containing equally many a’s and b’s

Problem 2

Graded by Chung-Man Tam and Andy Hsieh

Figure 2: 2-UCM accepting {a^{n}b^{n}a^{n} | n ≥ 0}

Extra credit problem

Figure 3: Finite parenthesis transducer

The finite transducer in Figure 3 solves the problem. Its initial state is labeled by A, and accepting states by A and D. To see that it indeed accepts and prints a balanced string of half the length of the original one must realize that the following invariant holds (we did not expect such an argument from those who solved the problem):

A When control resides at A, v is the input processed so far, and w is the output generated so far, then

(∃m, n) [ \begin{matrix}lp(v) = 2n ∧ rp(v) = 2m ∧ \\ lp(w) = n ∧ rp(w) = m ∧ \\ balanced(v \underbrace{) …)}_{|2n−2m|}) ⟺ balanced(w \underbrace{) …)}_{|n−m|}) \end{matrix} ]

B When control resides at B, v is the input processed so far, and w is the output generated so far, then

(∃m, n) [ \begin{matrix}lp(v) = 2n + 1 ∧ rp(v) = 2m ∧ \\ lp(w) = n ∧ rp(w) = m ∧ \\ balanced(v \underbrace{) …)}_{|2n+1−2m|}) ⟺ balanced(w \underbrace{) …)}_{|n−m|}) \end{matrix} ]

C When control resides at C, v is the input processed so far, and w is the output generated so far, then

(∃m, n) [ \begin{matrix}lp(v) = 2n ∧ rp(v) = 2m + 1 ∧ \\ lp(w) = n ∧ rp(w) = m ∧ \\ balanced(v \underbrace{) …)}_{|2n−2m−1|}) ⟺ balanced(w \underbrace{) …)}_{|n−m|}) \end{matrix} ]

D When control resides at D, v is the input processed so far, and w is the output generated so far, then

(∃m, n) [ \begin{matrix}lp(v) = 2n + 1 ∧ rp(v) = 2m + 1 ∧ \\ lp(w) = n ∧ rp(w) = m ∧ \\ balanced(v \underbrace{) …)}_{|2n−2m|}) ⟺ balanced(w \underbrace{) …)}_{|n−m|}) \end{matrix} ]

lp(v) counts the number of left paranthesis in the string v, and rp(v) counts the number of right parenthesis in v. The predicate balanced(v) holds if and only if v is a balanced string. v \underbrace{) …)}_{k} is the string obtained by

concatenating k right parenthesis to the end of v.