Example 7.3. Thus we have δ (q 0 , a, z) = {(q 1 , 0 z )}, δ (q 1 , a, 0) = {(q 1 , 00)},
etc. with δ (q 1 , λ, z) = {(q 0 , z)}. When you write this all out, you will see
that the pda is deterministic.
15. This is obvious since every regular language can be accepted by a dfa and
such a dfa is a dpda with an unused stack.
16. The basic idea here is to combine a dpda with a dfa along the lines of the
construction in Theorem 4.1, with the stack handled as it is for L 1 . It should
not be too hard to see that the result is a dpda.
Section 7.4
2. Consider the strings aabb and aabbbbaa. In the first case, the derivation must
start with
, while in the second
is the necessary first step.
But if we see only the first four symbols, we can-not decide which case
applies. The grammar is therefore not in LL(4). Since similar examples can
be made for arbitrarily long strings, the grammar is not LL(k) for any k.
4. Look at the first three symbols. If they are aaa, aab, or aba, then the string can
only be in L(a * ba). If the first three symbols are abb, then any parsable string
must be in L(abbb * ). For each case, we can find an LL grammar and the two
can be combined in an obvious fashion. A solution is
Looking at the first three symbols tells us if
is necessary.
The grammar is therefore LL(3).
7. For a deterministic CFL there exists a dpda. When this dpda is converted into
a grammar, the grammar is unambiguous.
9. (a)
etc. with δ (q 1 , λ, z) = {(q 0 , z)}. When you write this all out, you will see
that the pda is deterministic.
15. This is obvious since every regular language can be accepted by a dfa and
such a dfa is a dpda with an unused stack.
16. The basic idea here is to combine a dpda with a dfa along the lines of the
construction in Theorem 4.1, with the stack handled as it is for L 1 . It should
not be too hard to see that the result is a dpda.
Section 7.4
2. Consider the strings aabb and aabbbbaa. In the first case, the derivation must
start with
, while in the second
is the necessary first step.
But if we see only the first four symbols, we can-not decide which case
applies. The grammar is therefore not in LL(4). Since similar examples can
be made for arbitrarily long strings, the grammar is not LL(k) for any k.
4. Look at the first three symbols. If they are aaa, aab, or aba, then the string can
only be in L(a * ba). If the first three symbols are abb, then any parsable string
must be in L(abbb * ). For each case, we can find an LL grammar and the two
can be combined in an obvious fashion. A solution is
Looking at the first three symbols tells us if
is necessary.
The grammar is therefore LL(3).
7. For a deterministic CFL there exists a dpda. When this dpda is converted into
a grammar, the grammar is unambiguous.
9. (a)