Automata, Computability, and Formal Languages
1. Use the algorithm that we had in class to transform the
following context-free grammar into Chomsky normal form:
S --> AA, A --> aB, B --> bA, A --> ε,
B --> ε.
2. Use the general algorithm to design a pushdown automaton that
recognizes exactly the context-free language described in
3. For the context-free grammar described in Problem 1:
- draw a tree that describes the derivation of the
- use this tree to determine the
subdivision of this sequence into u, v, x, y, and z;
- for i
= 0 and i = 2, draw trees explaining how the corresponding
sequences uvixyiz can be derived in this
4. The sequence abaab is accepted by the following pushdown
Use the general algorithm that we described in class (and that
is described in the book) to list all the rules of the
corresponding context-free grammar which are needed to deduce
the sequence abaab. Draw a parse tree explaining how this
sequence is derived by using these rules.
- this automaton starts at state 0,
- when in state 0, the rule (a, ε) --> a leads to state 1,
- when in state 1, the
rule (b, a) --> b leads to state 2,
when in state 2, the rule (a,
ε) --> z leads to state 2 again,
- when in state 2,
the rule (a,
z) --> ε leads to state 3,
- when in state 3, the rule (b, b) -->
ε leads to the final state 1.
5. Let Na(s) denote the number of a's in a string s,
Nb(s) denote the number of b's, and
Nc(s) denote the number of c's.
Prove that the language consisting of all the words s for which
Na(s) = Nb(s) = Nc(s) (i.e., words
which have exactly as many a's as b's as c's)
cannot be recognized by a pushdown automaton.