--%>
Assignment Help - homework help

  Equivalence of CFGs and NPDAs, Context Free Grammars & Languages

Equivalence of CFGs and NPDAs:

Theorem (CFG ~ NPDA): L ⊆ A* is CF iff  ∃ NPDA  M which accepts L.

Proof: Given CFL L, let consider any grammar G(L) for L. Build NPDA M which simulates all possible derivations of G. M is essentially a single-state FSM, with state q which applies one of G’s rules at a time. The start state q0 initializes the stack with content S ¢, where S is the beginning start symbol of G, and ¢ is at bottom of stack symbol. This initial stack content signifies that M aims to read an input which is an instance of S. In common, the current stack content is a sequence of symbols which represent the tasks to be accomplished in the characteristic of LIFO order (or last-in first-out). The task on the top of stack, state a non-terminal X, calls for the subsequent characters of the input string to be an instance of X. Whenever such characters have been read and confirmed to be an instance of X, X is popped from the stack, and the new task on the top of stack is started. Whenever ¢ is on the top of stack, that is, the stack is empty, all tasks produced by the first instance of S have been successfully met, that is, the input string read so far is an instance of S. M moves to accept state and stops.

The given below transitions lead from q to q:

A) ε, X-> w for all rule X -> w. Whenever X is on the top of stack, substitute X by a right-hand side for X.
B) a, a -> ε for all a ∈ A. Whenever terminal a is read as input and a is as well on the top of stack, pop the stack.

Rule 1 reflects the given fact: one way to meet the task of finding out an instance of X as a prefix of input string not yet read, is to resolve all the tasks, in correct order, present in the right-hand side w of the production X -> w. M can be considered to be the non-deterministic parser for G. The formal proof which M accepts precisely L can be completed by the induction on the length of derivation of any w ∈ L. QED

Ex L = palindromes: G(L) = ( {S}, {0, 1}, { S -> 0S0, S -> 1S1, S -> 0, S -> 1, S -> ε}, S )

1746_Equivalence of CFGs and NPDAs.jpg

Pf <- (sketch): Given NPDA M, build CFG G which generates L(M).

For simplicity’s sake, convert M to have the given characteristics: (i) The single accept state, (ii) Empty stack before accepting, and

(iii) Each transition either pushes the single symbol, or pops a single symbol however not both.

For each pair of the states p, q ∈ Q, introduce non-terminal Vpq. L(Vpq ) = {w | Vpq ->* w} will be the language of all strings which can be derived from Vpq according to the productions of grammar G to be build. In particular, L(Vsf) = L(M), where s is the beginning state and f is the accepting state of M.

Invariant:

Vpq produces all the strings w which take M from p with an empty stack to q with empty stack.

The idea is to associate all Vpq to one other in a way which reflects how labeled paths and subpaths via M’s state space relate to one other. LIFO stack access entails: any w ∈ Vpq will lead M from p to q in spite of of the stack content at p and leave the stack at q in similar condition as it was at p. Various w’s ∈ L( Vpq) might do this in different manners that leads to different rules of G:

A) The stack might be empty only in p and in q, never in between. When so, w = a v b, for certain a, b ∈A, v ∈ A*. And M comprises the transitions (p, a, ε) -> (r, t) and (s,b, t) -> (q, ε). Add the rules: Vpq  -> a  Vrs  b

B) The stack might be empty at certain point between p and in q, in state r. For each triple p, q, r ∈ Q, add up the rules: Vpq -> Vpr  Vrq.

C) For each p ∈ Q, add up the rule Vpp -> ε .

The figure at left describes Rule1, at right Rule 2. If M comprises the transitions (p, a, ε) -> (r, t) and (s,b, t) -> (q, ε), then one way to lead the M from p to q with similar stack content at start and the end of journey is to break-up the trip into three successive parts: (i) To read the symbol ‘a’ and push ‘t’; (ii) Travel from r to s with similar stack content at the beginning and the end of this sub-journey; (iii)  To read the symbol ‘b’ and pop ‘t’.

1193_invariant.jpg

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.