1 Shagami

Pushdown Automata Homework Solutions

Loyola University Maryland > Department of Computer Science > Dr. James Glenn > CS 478 > Homework > Exam #1 Practice Problems > Solutions

Problem 0: Review old homeworks.

Problem 1: Give a regular expression that generates the language over the alphabet {a, b} where each b in the string is followed by exactly one or three a's (so e, aaa, and babaaa are in the language but baabaaa is not).

a*(b(a ∪ aaa))*

Problem 2: Give a nondeterministic finite automaton that accepts the language generated by the regular expression (a ∪ ba ∪ baaa)*.

The automaton in Problem 3 is what we want.

Problem 3: Convert the following NFA to a DFA that accepts the same language. (λ-transitions are the same as ε-transitions.)

Problem 4: Find a DFA equivalent to the following DFA that has as few states as possible.

Note that the DFA accepts exactly those strings that don't contain bb as a substring. We start by creating a list of strings by finding a string that drives the machine to each state: ε, b, a, ba, baa, baaa, and bb for states q0, ..., q6 respectively. From this list, only ε, b, and bb are pairwise distinguishable (suffix b distguishes ε from the other two and suffix ε distinguishes b from bb). All of the other strings (a, ba, baa, baaa) on the list are indistinguishable from ε: adding a suffix will result in a string that does not contain bb if and only if the suffix does not contain bb (because none of those strings contain bb themselves and since they don't end with a b, no suffix can introduce a bb substring at the boundary).

Problem 5: Find a regular expression that generates the language accepted by the following DFA.

Eliminate q2 first, which changes the transition from q1 to q0 to a ∪ ba*b. Eliminate q1 next, which changes the self loop on q0 to a ∪ b(a ∪ ba*b). The final regular expression is then (a ∪ b(a ∪ ba*b))*.

Problem 6: Show that the lanaguge defined by {banbam | m > n} is not regular.

Denote the language in question by L. Suppose that L is regular. Then, by the Pumping Theorem, there is a k ≥ 1 such that for any string w in L of length at least k, w can be written as xyz where |xy| ≤ k, |y| > 0, and for all i ≥ 0, xyiz is in L (*). Find the k promised by (*) and let w = bakbak+1. Then |w| = 2k+3 > k and w is in L since k+1 > k (there are more a's in the second part than in the first part). Therefore, since w satisfies the conditions of (*), there is a way to write w as xyz where where |xy| ≤ k, |y| > 0, and for all i ≥ 0, xyiz is in L (**). Because |xy| ≤ k, xy has to come from the bak part of w. There are two cases: x = e and then y contains the first b in w, but then xy2z has three b's and so is not in L, contradicting (**); otherwise y = aq for some q > 0, but then xy2z = bak+qbak+1 where k+qk+1 and so xy2z is not in L because it has too many a's in the first part, which contradicts (**) again. Both cases lead to contradictions, so we must reject our initial assumption that L is regular. Therefore, L is not regular.

Problem 7: Give a grammar that generates the same language as the regular expression (a + b)*(a* + (ba)*).

First, we construct a FA that accepts the given language:

Next we convert the FA to a CFG by making a rule for each transition. The rules have the "from" state on the left side and the symbol on the transtion and the "to" state on the right side. Finally, we add empty productions for the final states:
A → a A
A → b A
A→ B
A→ C
B→ a B
B→ ε
C→ b D
C→ ε
D→ a C

We can also do this directly from the regular expression:
V → W X (thinking of W as the (a + b)* part and X as the (a* + (ba)*) part.
W → a W
W → b W
W → ε
X → Y (thinking of Y as the a* option)
X → Z (thinking of Z as the (ba)* option)
Y → a Y
Y → ε
Z → b a Z
Z → ε

Problem 8: Create a pushdown automaton that accepts the language {02n1n | n > 0}. Show that your PDA accepts 000011 and that it rejects 0001.

Using Goddard's notation:

Using JFLAP's notation:

This PDA works like the PDA for 0n1n except that it pops two 0s off the stack for every 1 read. The PDA accepts 000011: (q0, 000011, ε) » (q1, 00011, 0) » (q1, 0011, 00) » (q1, 011, 000) » (q1, 11, 0000) » (q2, 1, 000) » (q3, 1, 00) » (q2, ε, 0) » (q3, ε, ε) » (q4, ε, ε) where q4 is an accepting state.

The PDA rejects 0001: the only possible sequence of states is (q0, 0001, ε) » (q1, 001, 0) » (q1, 01, 00) » (q1, 1, 000) » (q2, ε, 00) » (q3, ε, 0) where q3 is not an accepting state.

(Transitions in this form of PDA are specified by a combination of input symbol and symbol popped off the top of the stack, with Z for the bottom of the stack. The transitions also indicate what characters are pushed onto the stack. Note that a READ state can be simulated by reading an input symbol, popping off the top of ths stack, and pushing that character back on the state. A POP state can be simulated with a transition that reads no input (a λ-transition).)

Problem 9: Create a pushdown automaton that accepts the language {w ∈ {0,1}* | w has twice as many 0s as 1s}.

Using Goddard's notation:

Using JFLAP's notation:

This PDA works like the PDA for strings with an equal number of zeros and ones, except that instead of keeping track of (# of zeros) - (# of ones), it keeps track of 2*(# of ones) - (# of zeros). If that value is -n then there are n zeros on the stack and the PDA is in state q1. If that value is +n then there are n ones on the stack and the PDA is in state q4. When we read a zero then we push a zero if the stack is empty or already contains zeros; otherwise we pop a one. When we read a one then we push two ones (since the value of 2*(# of ones) - (# of zeros) goes up by 2) if the stack is empty or there are ones on the stack; otherwise there must be zeros on the stack so we pop two if possible, or if there is only one zero on the stack then we pop that zero and push a one.

In the PDA using Goddard's notation we are in the left side when we have seen too many ones (2*(# of ones) - (# of zeros) is positive) and in the right side when we have seen too many zeros. On the left, we push two ones for each one read. If we read a zero, we pop a one or transition to the other half of the machine if the stack was empty. On the right, we push a zero for each zero read and pop two zeros for each one read. If there weren't two zeros to pop then we transition to the other side of the machine.

Problem 10:

  • Give a grammar that generates postfix expressions using operators +, -, *, and /. Use the terminal "id" to stand for any variable name and "lit" to stand for integer literals.

    E → E E O
    E → lit
    E → id
    O → +
    O → -
    O → *
    O → /

  • Show a derivation of "id lit id + *" in your grammar.

    EE E O ⇒ id E O ⇒ id E E O O ⇒ id lit E O O ⇒ id lit id O O ⇒ id lit id + O ⇒ id lit id + *

Problem 11: Determine whether the grammar implicitly defined by the following rules is ambiguous. Prove your answer. If the grammar is ambiguous, determine whether the language it generates is inherently ambiguous.

It is ambiguous. Here are two leftmost derivations of ab:
S ⇒ AB ⇒ abAB ⇒ abB ⇒ ab
S ⇒ AB ⇒ B ⇒ abB ⇒ ab

This language the grammar generates is regular (check!) and so it is not inherently ambiguous -- we could constuct a DFA that accepts the language and convert that into an unambiguous CFG.

The finite automata on this page were drawn with JFLAP.

Тогда Стратмор понял, что Грег Хейл должен умереть. В «ТРАНСТЕКСТЕ» послышался треск, и Стратмор приступил к решению стоявшей перед ним задачи - вырубить электричество. Рубильник был расположен за фреоновыми насосами слева от тела Чатрукьяна, и Стратмор сразу же его .

Leave a Comment


Your email address will not be published. Required fields are marked *