120_PDA_CFG_CFL.md

Automata Theory(PDA CFG, Context Free Lnaguages):

CFG

• This grammar generates some strings which cannot be generated by regular language like equal number of zeros and ones. This will have a set of derivation rules where LHS is always a single variable and RHS will be a string of variables and terminals (e.g. A->B, B->BB | b ). Using these rules we derive strings from the start variable.
• We say that particular CFG G generates a string w only when we start from a start variable and using only the derivation rules of the grammar we can go to the string w. This procedure is called derivation. Note that in the derivation process we can only replace the variable in the string not the terminal symbol.
• At each step of derivation we will replace one of the variables in the current string with another variable or terminal symbol using the derivation rule.

CFG is closed under union, concatenation, star(this means repeated for zero or any number of times) operations but not for complement and intersection operations.

Leftmost derivation:

• Alway replacing the leftmost variable of the string with some valid terminal or variable symbol of the grammar is called Leftmost derivation. If there is more than one leftmost derivation possible then that particular grammar is ambiguous. Sometimes we can get unambiguous grammar by converting grammar to Chomsky Normal Form(CNF). But for some grammar, being ambiguous is necessary which can’t be converted using the CNF method.

Chomsky Normal Form(CNF)

• It is the same as CFG but with only two types of derivations allowed in the grammar, those are A->BC (this one with just two variables in the RHS)and B->b (this one is with just one terminal symbol on the RHS). So either we can replace the variable symbols in the string by a pair of variable symbols or by a single terminal symbol. The context-free grammar defined in this way will always be unambiguous.
• Every CFG has an equivalent CNF form. Every string w that is generated by CFG_CNF will be derived by using exactly (2|w| - 1) steps. This is a very useful property of the CNF form.

**How does it work? **

• Here note that to create a string of length n we need n variables. To construct a string with the n number variables it will take n-1 steps in the CFG_CNF form. This is because we need to use exactly one step to add one more variable to the generated string.
• In the first step we will generate two variables using some derivation A->BC. Suppose we have another derivation of the form B->DE, Then we can use that to generate DEC. By doing this for n-1 steps we will get a string of length n with only variables in it. Then We can use the derivations of the form B->b to replace each of the n variable symbols to the n terminal symbols which will take another n steps.
• This way each variable can be replaced by some terminal symbol. So to construct and replace all the n variables we will need exactly (n + (n-1)) steps. This is why we need a total of 2n-1 steps.

PDA- Push down automata

• Unlike DFA, This machine is by default a non deterministic machine, So it can have a set of possible moves(or transitions) for each input symbol it reads. The PDA also reads input symbols one by one and changes the state like the Finite Automata.
• But it has some extra capability called stack. This stack is very similar to the stack we learn about in the data structures or in programming languages. Whenever it wants to remember something like no of zeros in the input or trace of the states it went through. It can just push that information into the stack.
• The PDA is defined by the following tuples (Q, Sigma, Gama, Delta, start state, accept states). Q is the set of states of the machine just like DFA, Sigma is input symbols, Gama is the symbols that you can use in the stack, Delta is the transition function of the automata that defines the possible moves PDA can make for current state, input symbol and stack symbol. Other than these things there is also a start and accept state like other automatas.
• Whenever the stack is empty and no more symbols to read then the machine accepts that string. This machine is equivalent in power to CFG.

CFG to PDA

• Here PDA should accept all the strings that are generated by the Context Free Grammar. To achieve that machine will check whether we can derive an input string from the start variable. It first pushes the start variable to the stack. Then pops the topmost symbol in the stack if it is a variable then pushes the RHS value of that variable in a reverse order.
• We can easily construct a logic to push the RHS content in the reverse order. We can do that by simulating some Finite state Machine inside the PDA. Since the length of these derivation rules are contant we don’t need some extra memory to do this logic.
• When it is popping the top symbol from the stack, If that is terminal then match with the input symbol and move to the next input symbol. If the top symbol is terminal and does not match with the current input symbol then don’t accept the input. Otherwise continue this process.
• If there are more than one derivation rule for the same variable symbol then the machine will non-deterministically choose one of them. This shows that every CFG can be converted to equivalent PDA.

PDA to CFG

• Here we will create a variable A(pq) if and only if some string x can bring the machine from state p with empty stack to state q with empty stack. By proving the above statement we will prove that every PDA can be converted to CFG. This means if the PDA accepts some string x by going from the state p to the state q, then we will have some variable A(pq) that generates the string x.
• There will be two possible ways that the variable A(pq) can generate the string x, which are A(pq) -> aA(rs)b or A(pq) -> A(pr)A(rq).
• First derivation rule represents that by reading the input symbol a the PDA goes from the state p to the state r, then by reading some string y, it goes from the state r to the state s and then by reading the input symbol b it goes from the state s to the state q. Note if we follow the construction procedure then we will also generate the variable A(rs) which will generate the string y. So this first kind of derivation rule has both variables and terminals.
• Second case says that if there are two rules A(pr) and A(rq) in the grammar we can add a new derivation rule A(pq). The second derivation rule will have only variable symbols.

1. For each p,q,r,s ∈ Q, u ∈ Γ, and a,b ∈ Σε, if δ(p,a,ε) -> (r,u) and δ(s,b,u) -> (q,ε), put the rule A(pq) → aA(rs)b in G. Here note that we assume we already have a variable A(rs) grammar.

2. For each p,q,r ∈ Q, put the rule A(pq) → A(pr)A(rq) in G.

3. For each p ∈ Q, put the rule A(pp) → ε in G.

• By using the above three rules we can generate the CFG G from the description of some PDA P. Here δ(s,b,u) -> (q,ε) means PDA can go from the state s to the state q by reading the input symbols b and popping the symbol u from the top of the stack. The empty string symbol means during this transition the PDA does not push any symbol to the stack.
• If two transitions as mentioned in the first construction rule exist in the description of the PDA then we will add the rule A(pq) as mentioned in the first rule.
• Second construction rule says that if we can go from the state p to the state q and if we can go from the state q to the set r then add the derivation rule of the second kind A(pq) -> A(pr)A(rq).
• Third construction rule represents that we can go from any state p to itself by reading the empty string input symbol.

PDA closure

• Every Regular language is a CFL. Intersection of CFL and Regular language is a CFL. This is true because PDA can internally simulate DFA.
• Intersection of one CFL to another CFL is not a CFL because here we will not be able to operate on two CFL with a single stack(this is not exactly correct proof). In the formal case we can simulate DFA without another stack. CFL is closed under union, concatenation and star.

Pumping lemma for CFG

• There are some languages that cannot be generated by CFG. The language that can be generated by CFG will have certain properties. If anyone of this property is missing then CFG doesn’t generate that language.
• There are three rules all based on writing a string of length at least p(pumping length) in the format u(v^i)x(y^i)z. where i>=0 and |vy|>0 and |vxy|<=p and p = b^(|V| +1). Here b is the maximum number of symbols allowed in the RHS of the rule and |V| is the total number of variables in the grammar.
• We can get the pumping length p from the parse tree of the context free grammar. If there are n variables in the grammar, but the parse tree of height n+1 then at least one variable must be repeated at some level the parse tree. The Parse tree is like the binary tree we see in programming languages but it represents the derivation of some string from the start variable to the sequence of terminal symbols. We can use that repeating variable to generate (v^i)x(y^i).
• Core idea: In some way this pumping lemma verifies that if some repeating substring is there in the string or not. If such a repeating substring exists in the string that we need to generate then we can use the loop kind of logic to generate that repeating substring.
• Examples of non CFL are (a^p b^p c^p) and (ww) where the same string w is repeated two times.

But note that (ww^R) is CFG because at each step we will non deterministically assume that we are at the middle of the input and pop the stack to check the reverse. So there will be multiple copies of the stack. But this is not the case for (ww) we can prove this by pumping lemma.

DPDA

• This is a deterministic version of PDA. This is less powerful than actual PDA. This will be equivalent to DPDA. At any moment of time there will be at most one way to proceed based on the transitions. In DPDA empty input string transitions are allowed unlike DFA. But to avoid non determinism at most one of four possible transitions will be not null for any state transitions from p to q.
• If δ(s,b,u) -> (q,ε) means PDA can go from the state s to the state q by reading the input symbols b and popping the symbol u from the top of the stack. The empty string symbol means during this transition the PDA does not push any symbol to the stack.
• For every state q, input symbol a and stack symbol x, at most one of the following four rules should be non empty δ(q,a,x), δ(q,a,ε), δ(q,ε,x), δ(q,ε,ε). Otherwise it would impose the non deterministic behaviour on the deterministic machine.

We use some lemmas in arguments involving DPDA that are given below.

• Every DPDA has an equivalent DPDA that always reads an entire input string.
• The class of DCFL is closed under complementation. We will prove this by converting DPDA to avoid looping, hanging and doing multiple actions at same time(non reading states). For example non reading states won’t pop and push to the stack in a single transition.
• Then we can just swap the final and non final states to get the complemented DPDA. DCFL is not closed under union, intersection, star and reversal.
• w is DCFL if and only if the end marked w is DCFL. We can prove this by showing that we can convert DPDA which accepts the string w with end marks can be converted to DPDA that will accept just w without endmark. We will prove the reverse also.
• To prove the equivalence of DCFG with DPDA we use the endmarkers. In the non deterministic version we can non deterministically guess the end of the input to empty the stack. So we can accept when the stack is empty. But in the deterministic version this logic doesn’t work quite well.
• Without endmarkers the DCFG only generates a subset of the languages recognised by the DPDA. That subset corresponds to the prefix-free languages. The prefix-free language means no string in the language is a prefix of some other string in the same language.

DCFG

• DCFG is a CFG such that every valid string has a forced handle.
• For CFG grammar we had a set of derivation rules and derived strings until we only had terminals. But here we take the bottom up approach. We check whether the string is in the grammar by using a series of reductions to get the start variable. Together with the concept of a forced handle(unambiguous grammar) where handles are unique even when we extend(the strings xhy or xhy’ should not affect the handle h) the string. Using this way we can achieve determinism here. We use these handles to replace them with some LHS variable of some derivation rule. We continue this process until either we get the start variable(accept) or the case where there are no handles(non accept). We use the leftmost reduction to find the handles.
• DCFG is not closed under union,intersection, concatenation, star and reversal operations. DCFG is closed under complement.
• DCFG without end markers only generates a subset of DCFL which are prefix free. All endmarked languages are prefix free.

DK test and Forced handle

• In the reduction rules we call the h together with its reducing rule T -> h, a handle when we can reduce from the h to the variable symbol T in the reduction process or in other words when we can generate a string h from the variable T.
• The DK test says we can design a DFA DK that can identify handles such that it will accept z if z is the prefix of some valid string v=zy and z ends with the handle of v. Also using this idea we can build a DPDA for the corresponding DCFG.
• DFA DK should have a single handle associated with its accept state and no accept state should have an outgoing path that leads to another accept state. If we can construct such a DK then grammar is DCFG.
• For this we first construct NFA J which accepts any string z which ends with a handle. Then modify it to get NFA K which will find a handle from v=zy. This K will have two kinds of moves: shift-moves and empty string moves. Then we can convert this NFA to DFA.
• G passes the DK test if and only if it is DCFG. After converting NFA to DFA To pass the DK test it has to satisfy two conditions:

1. No accepted state should have more than one dotted rule.
2. No dotted rule of the form (u.av) in the accepted state. But there can be an outgoing rule with a variable as an input.

• Below grammar is DCFG: passes DK test(because it has a forced handle. But if you remove symbols 1 and 2 it won’t have forced handle so will fail DK test)

R →1S|2T

S →aSb|ab

T →aTbb|abb

DCFG and DPDA equivalence

• Endmarkers are necessary to prove this equivalence. To prove this we will need the DFA DK to find handles from the input string to apply reduction. To unambiguously find handles of string, they should have a forced handle(means single parse tree for deriving string).
• DCFG has very important practical applications. Their membership(whether string is in grammar) checking algorithms are based on DPDA so they are efficient so they are used in parsing in the compilers of the programming languages.

DCFG to DPDA

• We will use DFA DK for this. We will iterate through the input string multiple times each time reducing one handle. For this we have to store the modified string somewhere. We can push whatever state we go through to the stack and when we reach the accept state we will know the length of the accept state and we pop that many items from the stack.
• We will continue this process until we read the full input at the end when P pushes the start symbol on the stack that means the string is accepted.

DPDA to DCFG

• We modify PDA P to empty stack and go to q(accept) when it reads an end marker symbol and it is in one of the original accept states of PDA P. Then we apply mostly similar grammar construction as PDA to CFG. CFG’s derivation closely corresponds to DPDA’s computation. Because CFG at each step derives some new string from old string using derivation. DPDA does the same thing but ensures determinism by allowing at most one possible transition from any state.Here don’t confuse with reduction that is part of DCFG DK test not DPDA. In PDA to CFG we add variables of form A(pq) -> A(pr)A(rq) where stack empties at the midway. If stack empties multiple times then that is an ambiguous grammar which will generate multiple parse trees. To avoid that we will modify the grammar to divide the computation at the very last point where stack empties midway. We combined the rules in the PDA to CFG to single rule1-2. For each p,q,r,s,t ∈ Q, u ∈ Γ, and a,b ∈ Σε, if δ(r,a,ε) = (s,u) and δ(t, b, u) = (q,ε), put the rule Apq → A(pr)aA(st)b in G.
• We will prove that this will create unambiguous grammar. Here in A(pr)A(rq) we replaced the A(rq) using the first rule of the PDA to the CFG conversion. Then we will use the DK test to show that grammar G is deterministic. We will do this by showing how P operates on the valid string by extending its input symbols and transition function to deal with variables of kind A(pq) in the string. We have variables in the string because we may do the reduction using DPDA to check whether it accepts the string of grammar G.
• If it passes the DK test the DPDA which accepts the grammar of the form A(pq) is DCFG. Hence we proved that we can convert the DPDA to the DCFG.

Parsing and LR(k) Grammar

• DCFG is used for parsing the programming language syntax. But one problem is they should have forced handles. To avoid this complication the closest solution which can be directly converted to DPDA is LR(k) grammars.
• In an LR(k) grammar, a handle may also depend on symbols that follow the handle, but only on the first k of these. So it is also CFG but strings have forced handles for lookup up to k symbols. DCFG = LR(0). Here L statanda for left to right and R for right most derivation(or leftmost reduction). It is a bottom up approach because it uses reduction. Post order traversal of a parse tree.

LL(k)

• Here first L stands for left to right and second L for left most derivation(or rightmost reduction). It is a top down approach. Expands variables into terminals. Uses pre order traversal of a parse tree.

PUA

• Pull-up automata use a queue instead of stack. This machine is equivalent to the Turing machine in power. It uses an infinite queue instead of a stack.