Question

Models of Languages and Computations

1.Consider the PDA P = (Q, Σ, Γ, δ, q0, Z0, F) where:
• Q = {q0, q1, q2} is the set of states.
• Σ = {a, b, c} is the input alphabet.
• Γ = {X} is the stack alphabet,
• q0 is the initial state.
• Z0 is the start symbol on the stack.
• F = ∅ is the (empty) set of accepting states.
• δ, the transition function is given by:
1. δ(q0, a, Z0) = {(q1, Z0)}
2. δ(q0, a, X) = {(q1, X)}
3. δ(q1, b, Z0) = {(q0, XZ0)}
4. δ(q1, b, X) = {(q0, XX)}
5. δ(q0, ϵ, Z0) = {(q2, Z0)}
6. δ(q0, ϵ, X) = {(q2, X)}
7. δ(q2, c, X) = {(q2, ϵ)}
8. δ(q2, ϵ, Z0) = {(q2, ϵ)}
a. Is P deterministic? Yes or no, justify your answer
b. If the acceptance criterion is by empty stack, does P accept abcc? Show your work using instantaneous descriptions.
2. We know that context-free Languages are not closed under the intersection operation. However, if L is a context-free language, and R is a regular language, then the intersection L ∩ R is context-free. This problem illustrates this result. Construct a PDA for the language L ∩ R for the special case where the alphabet is {0, 1}, L = n > 0, and R = w . Hint: First design a PDA for L and a DFA for R. Then combine the ideas into a PDA for L ∩ R.

Answer 1

The PDA provided is not deterministic due to epsilon transitions. Using instantaneous descriptions, it is shown that the PDA accepts the string 'abcc' based on the empty stack acceptance criterion.

Step-by-step explanation:

The given PDA is not deterministic because there are transitions involving the empty string ε (epsilon transitions). Specifically, δ(q0, ε, Z0) and δ(q0, ε, X) can occur without consuming any input symbols, leading to non-deterministic behavior as the machine can make these transitions at any point without any specific requirements on the input.

To determine if P accepts abcc by empty stack, we use instantaneous descriptions (ID):

1. (q0, abcc, Z0)
2. (q1, bcc, Z0)
3. (q0, cc, XZ0)
4. (q2, cc, XZ0)
5. (q2, c, Z0)
6. (q2, ε, ε)

Since we reach an empty stack and an ID of the form (q2, ε, ε), P accepts abcc by empty stack.