Monday, 24 June 2013

CFG/CFL to NPDA

``` Given a Context Free Grammar, CFG, in Greibach Normal Form, A -> aB1B2B3...
Construct an NPDA machine that accepts the same language as that grammar.

We are given G = ( V, T, P, S ) and must now construct
M = ( Q, Sigma, Gamma, delta, q0, Z0, F)
Q = {q}  the one and only state!
Sigma = T
Gamma = V
delta is shown below
q0 = q
Z0 = S
F  = Phi  NPDA will "accept on empty stack"

Now, for each production in P (individual production, no vertical bars)

A -> a gamma  constructs
|    |   |
|    |   +-------------+
|    |                 |
+-----------+          | gamma is a possibly empty, sequence of
|      |          |       symbols from Gamma
+---+  |          |
|  |          |
V  V          V
delta(q, a, A) = {(q, gamma), more may come from other productions}

If gamma is empty, use epsilon as in (q, epsilon)
Finished!

An example:  Given production      Resulting delta             #
C -> 0 C T            delta(q, 0, C) = (q, CT)    1
C -> 0 T T            delta(q, 0, C) = (q, TT)    2
S -> 0 C              delta(q, 0, S) = (q, C)     3
S -> 0 T              delta(q, 0, S) = (q, T)     4
T -> 1                delta(q, 1, T) = (q, #e)    5

NPDA running with input tape 0011 and initial stack S
0011      |S|
^         | |

delta #3 and #4 both apply, resulting in two stacks and advancing input
0011      |C|         |T|
^        | |         | |

delta #1 and #2 apply to the first stack, the second stack dies, advancing
0011      |C|   |T|  dies
^       |T|   |T|
| |   | |

delta #5 applies to the second stack, the first stack dies, advancing
0011     dies   |T|
^            | |
delta #5 applies, the stack becomes empty and advance to beyond input
0011            | |
^           | |
accept input string.

Another conversion algorithm that uses more states, three to be exact,
is somewhat simpler.

We are given G = ( V, T, P, S ) and must now construct

M = ( Q, Sigma, Gamma, delta, q0, Z0, F)
Q = {q0, q1, q2}
Sigma = T
Gamma = V union {Z} where Z not in V (an extra symbol)
delta = Q x (Sigma union epsilon) x Gamma -> Q x Gamma  shown below
q0 = q0
Z0 = Z  (to get the NPDA started)
F  = q2  the final accepting state

Two predefined transitions, the start and the accept are:
delta(q0, epsilon, Z) = { (q1, SZ) }
delta(q1, epsilon, Z) = { (q2, Z) }

For every rule in P , Greibach normal form, A -> aU generate
delta(q1, a, A) = { (q1, U) } union all other sets from (q1, a, A)

Note: The empty string must be removed to create Greibach normal form,
thus a grammar that initially accepted the empty string needs the
extra transition
delta(q0, epsilon, Z) = { (q2, Z) }

The conversion is proved to simulate a leftmost derivation.```