Question

For a given language L = { w | n_a(w) + n_b(w) = n_c(w) } where S = G = {a, b, c} Looking for answer to 3

1. Construct a PDA M that accepts L with S = G = {a, b, c}
2. Show the sequence of instantaneous descriptions for the acceptance of acacbcbc by M in 1).
3. Give a CFG G that generates L, L(G) = L.

Answer 1

Language L = { w | n_a(w) + n_b(w) = n_c(w) } where S = G = {a, b, c}

1 ) pushdown automata is below

how the PDA work ( Z0 is the initialized stack symbol,

                               E denote epsilon , delete one element from stack )

* initial stak element is

*when a or b come , we push the element to stack.

*when C come above a or b in stack , delete one element from stack.

*when C come above Z0 we push C to stack.

*when a or b come above C in stack , delete one element.

*when c come above c n stack , push c to stack

*when come above Z0 go to accept state

2 ) sequence of instantaneous descriptions for the acceptance of acacbcbc

    initial stack symbol is Z0.

    "a " come push to stack

    " c " come delete "a"

     "a " come push to stack

     " c " come delete "a"

      "b " come push to stack

     " c " come delete "b"

    "b " come push to stack

     " c " come delete "b" ( now only Z0 is in stack )

     " come above Zo" ----> go to accept state

3) CFG G that generates L, L(G) = L

S -> aX/ bX /

X- >S A / A S

A -> c

the above grammar only accept string with number of " c " = number of "a"+ number of " b "