undefined | unit 4 parsing and pushdown automata

ALC

Unit-4Parsing and Pushdown Automata Q1) Explain pushdown automata?A1) Pushdown automata It is a way to implement a context-free grammar as we design DFA for a regular grammar. A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.Basically a pushdown automaton is −"Finite state machine" + "a stack"A pushdown automaton has three components −● an input tape,● a control unit, and● a stack with infinite size.The stack head scans the top symbol of the stack.A stack does two operations −● Push − a new symbol is added at the top.● Pop − the top symbol is read and removed.A PDA may or may not read an input symbol, but it has to read the top of the stack in every transition.

PDA

Figure Basic Structure of PDAA PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −● Q is the finite number of states● ∑ is input alphabet● S is stack symbols● δ is the transition function: Q × (∑ ∪ {ε}) × S × Q × S*● q0 is the initial state (q0 ∈ Q)● I is the initial stack top symbol (I ∈ S)● F is a set of accepting states (F ∈ Q)The following diagram shows a transition in a PDA from a state q1 to state q2, labeled as a,b → c −

Transition in a PDA

Figure exampleThis means at state q1, if we encounter an input string ‘a’ and top symbol of the stack is ‘b’, then we pop ‘b’, push ‘c’ on top of the stack and move to state q2. Q2) Describe deterministic PDA?A2) Deterministic PDA● Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. ● Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top.● A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. ● This is where it differs from the nondeterministic pushdown automaton. A deterministic pushdown automata M can be defined as 7 tuples - M = (Q, ∑, T, q0, Z0, A, δ)Where,● Q is finite set of states,● ∑ is finite set of input symbol,● T is a finite set of stack symbol,● q0 ∈ Q is a start state,● Z0 ∈ T is the starting stack symbol,● A ⊆ Q, where A is a set of accepting states,● δ is a transition function, where:δ :(Q X ( ∑ U {ε }) X T ) ➝ p(Q X T* ) Q3) Design PDA for Palindrome strips?A3) PDA for PalindromeSuppose the language consists of string L = {aba, aa, bb, bab, bbabb, aabaa, ......].The string can also be odd palindrome or even palindrome. The logic for building PDA is that we will push a symbol until half of the string onto the stack, then we will read each symbol and then perform the pop operation. To see whether the symbol that is popped is similar to the symbol that is read, we will compare. We expect the stack to be empty if we reach the end of the input. This PDA is a non-deterministic PDA because the middle of the given string is based and reading the string from left and matching it with from right (reverse) direction leads to non-deterministic moves. Here is the ID

δ(q1, a, Z) = (q1, aZ)

δ(q0, b, Z) = (q1,bZ)

δ(q0, a, a) = (q1,aa)

δ(q1, a, b) = (q1, ab)

δ(q1, a, b) = (q1, ba)

δ(q1, b, b) = (q1, bb)

(pushing the symbol onto the stack)

δ(q1, a, a) = (q2, ε)

δ(q1, b, b) = (q2, ε)

δ(q2, a, a) = (q2, ε)

δ(q2, b, b) = (q2, ε)

δ(q2, ε, Z) = (q2, ε)

(popping the symbol on reading the same kind of symbol) Simulation of abaaba

δ(q1, abaaba, Z) Apply rule 1

⊢ δ(q1, baaba, aZ) Apply rule 5

⊢ δ(q1, aaba, baZ) Apply rule 4

⊢ δ(q1, aba, abaZ) Apply rule 7

⊢ δ(q2, ba, baZ) Apply rule 8

⊢ δ(q2, a, aZ) Apply rule 7

⊢ δ(q2, ε, Z) Apply rule 11

⊢ δ(q2, ε) Accept

Q4) Explain top - down parsing?A4) Top - down parsingRecursive or predictive parsing is known as top-down parsing. The parsing begins with the start symbol in the top-down parsing and transforms it into the input symbol. The top-down parser is the parser that, by expanding the non-terminals, generates a parse for the given input string with the aid of grammar productions, i.e. it begins from the start symbol and ends on the terminals. Parse Tree The input string representation of acdb is as follows:

There are 2 types of additional Top-down parser: Recursive descent parser, and Non-recursive descent parser.

Recursive descent parser:

It is also known as Brute force parser or the with backtracking parser. Basically, by using brute force and backtracking, it produces the parse tree. A top-down parsing technique that builds the parse tree from the top and reads the input from left to right is recursive descent. For any terminal and non-terminal entity, it uses procedures. The input is recursively parsed by this parsing technique to make a parse tree, which may or may not require back-tracking. But the related grammar (if not left-faced) does not prevent back-tracking. Predictive is considered a type of recursive-descent parsing that does not require any back-tracking. As it uses context-free grammar that is recursive in nature, this parsing technique is called recursive. 2. Non-recursive descent parser:It is also known with or without a backtracking parser or dynamic parser, LL(1) parser or predictive parser. It uses the parsing table instead of backtracking to create the parsing tree. Q5) What do you mean by bottom - up parsing?A5) Bottom - up parsing Bottom up parsing is also known as parsing for shift-reduce. Bottom-up parsing is used to build an input string parsing tree. The parsing begins with the input symbol in the bottom up parsing and builds the parse tree up to the start symbol by tracing the rightmost string derivations in reverse. Parsing from the bottom up is known as multiple parsing. That are like the following:

Shift-Reduce Parsing

Operator Precedence Parsing

Table Driven LR Parsing

● LR( 1 )● SLR( 1 )● CLR ( 1 )● LALR( 1 ) Shift reduce parsing ● Shift reduction parsing is a mechanism by which a string is reduced to the beginning symbol of a grammar. ● Using a stack to hold the grammar and an input tape to hold the string, Shift reduces parsing.

● The two acts are done by Shift Decrease Parsing: move and decrease. This is why it is considered that shift reduce parsing. ● The current symbol in the input string is moved into the stack for the shift operation.● The symbols will be substituted by the non-terminals at each reduction. The mark is the right side of manufacturing and the left side of output is non-terminal.operator precedence parsingThe grammar of operator precedence is a kind of shift reduction system of parsing. It is applied to a small grammar class of operators. A grammar, if it has two properties, is said to be operator precedence grammar: ● There's no R.H.S. of any production. ● There are no two adjoining non-terminals. Operator precedence can only be defined between the terminals of the grammar. A non-terminal is overlooked. The three operator precedence relations exist: ● a ⋗ b suggests that the precedence of terminal "a" is greater than terminal "b" ● a ⋖ b means the lower precedence of terminal "a" than terminal "b" ● a ≐ b indicates that all terminals "a" and "b" have the same precedence. LR parsers ● In the LR parser, “ L” means left to right scanning of any input .● One form of bottom up parsing is LR parsing. It is used to evaluate a broad grammar class. ● R" stands for the construction of a proper reverse derivation. ● "K" is the number of look-ahead input symbols used to make a number of parsing decisions. LR parsing is divided into four parts: parsing for LR (0), parsing for SLR, parsing for CLR and parsing for LALR. Q. 6) Explain palindrome example of PDA ?Ans : Palindrome example

{x ∈ {a,b,c}* : x = wcwR for w ∈ {a,b}*}

The machine pushes a's and b's in state s, makes a transition to f when it sees the middle marker, c, and then matches input symbols with those on the stack and pops the stack symbol. Non-accepting string examples are these:Ε in state sAb in state s with non-empty stackAbcab in state f with unconsumed input and non-empty stackAbcb in state f with non-empty stackAbcbab in state f with unconsumed input and empty stackObserve that this PDA is deterministic in the sense that there are no choices in transitions. The second example is:

{x ∈ {a,b}* : x = wwR for w ∈ {a,b}*}

This PDA is identical to the previous
one except for the ε-transition

Nevertheless, there is a significant difference in that this PDA must guess when to stop pushing symbols, jump to the final state and start matching off of the stack. Therefore, this machine is decidedly non-deterministic. In a general programming model (like Turing Machines), we have the luxury of preprocessing the string to determine its length and thereby knowing when the middle is coming. Q7) What is the difference between top down and bottom up parsing?A7) Differences are as:

Top down parsing	Bottom up parsing
It is a parsing technique that first looks at the highest level of the parse tree and, using the grammar rules, works down the parse tree.	It is a parsing technique that first looks at the lowest level of the parse tree and, using the grammar rules, works up the parse tree.
Top-down parsing tries to locate most of the input string derivations to the left.	It is possible to describe bottom-up parsing as an attempt to decrease the input string to initiate a grammar symbol.
In this parsing technique, we begin top-down parsing from top (parse tree start symbol) to down (parse tree leaf node).	In this parsing technique, we begin to parse from the bottom (parse tree leaf node) to the top (parse tree start symbol) in the bottom-up manner.
Left Most Derivation is used for this research methodology.	This technique of parsing uses the most accurate derivation.
In order to build the string, the key decision is to choose which production rule to use.	Choosing when to use a development rule to decrease the string to get the starting symbol is the key decision.

Q8) What are the equivalence of CFG’s and PDA’s?A8) Equivalence of CFG & PDAThe purpose is to show that all the following three language groups are the same class. 1. The context-free languages (The language defined by CFG’s). 2. The languages that are accepted by empty stack by some PDA. 3. The languages that are accepted by final state by some PDA.

We have already shown that (2) and (3) are the same. Now, we prove that (1) and (2) are same. Recall the following theorem from the chapter context-free grammar. Theorem: Let G = (V, T, R, S) be a CFG, and suppose there is a parse tree with root labeled by variable A and with yield w(∈ T ∗ ). Then there is a leftmost derivation A ∗⇒lm w in grammar G. Q9) Construct a PDA for language L = {0n1m | n >= 1, m >= 1, m > n+2}A9)The first 0's are pushed into the stack. Two 1's are ignored when the 0's are over. A 0 is then popped out of the stack for every 1 as an input. If the stack is empty and there are still some 1s left, then they are all ignored. Step-1: Push it onto the stack upon receiving 0. Ignore it and go to the next state upon receiving 1, Step-2: Ignore it on receiving 1, and go to the next state. Step-3: Pop a 0 from the top of the stack and go to the next state upon receiving 1, Step-4: Pop a 0 from the top of the stack after receiving 1, If the stack is empty, enter it on receiving 1 and go to the next state. Step-5: Ignore it on receiving 1. If the input is completed, go to the last state.

Q10) The transition a Push down automaton makes is additionally dependent upon the:a) stackb) input tapec) terminalsd) none of the mentioned A10) Correct answer is “a “. Explanation: A PDA is a finite machine with additional storage for the stack. Not only the input and the correct state, but also the stack is the basis for its transitions.

Sign Up