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 )
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’.
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.
tutorsglobe.com digestion in small intestine assignment help-homework help by online carbohydrates tutors
Opening and closing stocks cost audit program - the opening stock is not excessively large compared with the volume of production throughout the year;
Theory and lecture notes of Changes in Macro-Economy all along with the key concepts of changes in macro-economy, Occupational Distribution of the Labor Force. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Changes in Macro-Economy.
eeg (electro encephalo graphy) is employed to diagnose dissimilar type of epilepsy and in the location of the focus in the brain causing the epilepsy.
tutorsglobe.com lamarckism assignment help-homework help by online theories of evolution tutors
tutorsglobe.com merits of mixed economy assignment help-homework help by online mixed economy tutors
human engineering an essential step related to the human factors. is a multidisciplinary activity that applies knowledge derived from psychology and technology to specify and design high quality hci?
tutorsglobe.com labor assignment help-homework help by online kinds of factors of production tutors
www.tutorsglobe.com offers Types of Requirement homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Elastic Constants of Crystals tutorial all along with the key concepts of Experimental determination of elastic constants, Elastic waves in cubic crystals, Elastic isotropy and Cauchy relation
Objectives of Cost Accounting - To determine the cost of production on per unit basis, for instance cost per liter, cost per kg, cost per meter, cost per ton etc.
tutorsglobe.com significance of factoring assignment help-homework help by online factoring tutors
Nature of Operating Costing - The major purpose of operating costing is to calculate the cost of the services that are offered by the organization.
Case study of viral diseases tutorial all along with the key concepts of Acquired Immunodeficiency Syndrome (AIDS), Virology, Major Signs, Diagnosis, Treatment, Vaccines, Rabies, Epidemiology, Pathogenesis and Pathology, Clinical Features/Symptoms, Incubation Period, Isolation/Diagnosis and Control of rabies
Theory and lecture notes of Difference between File system & DBMS all along with the key concepts of difference between file system & dbms, File System, DBMS, Advantages of DBMS, Functions of DBMS. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Difference between File system & DBMS.
1940639
Questions Asked
3689
Tutors
1448284
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!