Week 2 - PDA versus CFL

Question 1

TRUE OR FALSE: If a language is a context-free language then there exists a PDA that recognises it.

Answer 1

TRUE.

Question 2

What are the steps for converting a context-free-language to a pushdown automoton?

Answer 2

First we add 3 states: the initial state, the final state and a middle state. The transisition between qStart and qMiddle should be (ε, ε) -> S$ such that it doesn’t read anything from the input or stack or delete anything from the stack, and writes S and then $ to the stack.
The transition between qMiddle and qAccept should be (ε, $) -> ε.

Next qMiddle should have a loop transition to itself that mimics all the rules of the grammer. The transition will have a label for each rule in the grammer. The rules are converted as follows:
S -> A
to
(ε, S) -> A
By the end of this, it should have as many labels as rules. You also add labels to that transition for each non terminal symbol that is:
(a, a) -> ε where a is a given non terminal symbol

Next we expand the complicated transitions. Any transition label that has more than one symbol written at a time to the stack should be split for each symbol it writes to the stack. Only the first of the transistions should delete the top item of the stack. Each of these transitions should go between new states that bridge the gap between the current state and transition state:
e.g.
(ε, S) -> ABC
becomes
(ε, S) -> A Note this one is the only one that deletes S
(ε, ε) -> B
(ε, ε) -> C

Now you have a PDA.

Question 3

TRUE OR FALSE: If a language is recognised by a PDA, then it cannot be recognised as a CFL.

Answer 3

FALSE.

Question 4

How to convert a PDA to a CFL?

Answer 4

Lemma 2.27

Question 5

TRUE OR FALSE: All deterministic finite automata are also pushdown automatas.

Answer 5

TRUE.

Question 6

TRUE OR FALSE: All pushdown automatas are also deteministic finite automata.

Answer 6

FALSE.