UNIT IV-TOC

 Unit-IV

Pushdown Automata, CFL And NCFL Definitions, Deterministic PDA, Equivalence of CFG and PDA & Conversion, Pumping lemma for CFL, Intersections and Complements of CFL, Non-CFL.

4.1)Pushdown Automata

·       The pushdown automaton is in essence a nondeterministic finite automata with ε-moves permitted and one additional stack capability on which it can store a string of “stack symbols”.

·       The presence of a stack means that, unlike the finite automaton, the pushdown automaton can remember an infinite amount of information.

·       However, unlike a general-purpose computer, which also has the ability to remember arbitrarily large amount of information, the pushdown automaton can only access the information on its stack in a LIFO (last-in-first-out) way.

·       There are languages that could be recognized by some computer program, but are not recognizable by any pushdown automaton. In fact, pushdown automata recognize all and only the context-free language.

·       While there are many languages that are context-free, including some we have seen that are not regular languages, there are also some simple-to-describe languages hat are not context-free.

·       For an example of non-context free language is M = {aⁿbⁿcⁿ | n ≥ 1}, The set of strings consisting of equal groups of a’s, b’s and c’s.

Figure: A pushdown automata is essentially a finite automata with a stack data structure

·       The informal way of pushdown automata representation is as represented in the above figure. Which consist a “Finite-state control” reads inputs, one symbol at a time.

·       The pushdown automata are allowed to observe the symbol at the top of the stack and to base its transaction on its current state, the input symbol, and the symbol at the top of the stack.

·       Alternatively, it may make a “spontaneous” transition, using ε as its input instead of an input symbol. In one transition, the pushdown automata:

• Consumes from the input the symbol that it uses in the transition. If ε is used for the input, then no input symbol is consumed.
• Goes to a new state, which may or may not be the same as the previous state.

For example, when a string ‘w’ from the language L = {aⁿbⁿ: n≥0}, we must not only check that all a’s precede the first b, we must also count the number of a’s. Since n is unbounded, this counting cannot be done with a finite memory thus this CFL is not proceeded with finite machine or finite automata.

So solve this problem we want a machine that can count without limit. We might try to solve this problem with a stack as a storage mechanism that allowing unbounded storage that is restricted to operating like a stack. The resulting class of machine called Pushdown Automata.

Hence the pushdown automaton is essentially an ε-NFA with addition of a stack. The stack can be read, pushed, and popped only at the top, just like the “stack” data structure.

4.2)CFL And NCFL Definition

Difference between CFL and NCFL

Feature	CFL (Context-Free Language)	NCFL (Non-Context-Free Language)
Definition	A language that can be generated by a Context-Free Grammar (CFG).	A language that cannot be generated by any Context-Free Grammar.
Automaton	Accepted by Pushdown Automaton (PDA).	Not accepted by PDA (requires stronger models like Turing Machine or Linear Bounded Automaton).
Grammar Type	Type-2 language in Chomsky Hierarchy.	Lies beyond Type-2, needs more powerful grammars.
Complexity	Handles nested structures and 2-way dependencies.	Handles more complex dependencies (e.g., 3 or more equal counts, string duplication).
Examples	L={anbn∣n≥0}L = \{a^n b^n \mid n \geq 0\}L={anbn∣n≥0} (equal a’s and b’s), Palindromes.	L={anbncn∣n≥0}L = \{a^n b^n c^n \mid n \geq 0\}L={anbncn∣n≥0}, L={ww∣w∈{a,b}∗}L = \{ww \mid w \in \{a,b\}^*\}L={ww∣w∈{a,b}∗}.
Applications	Used in compilers, parsing, programming languages.	Found in problems requiring higher computational power, beyond PDA capability.

 

 

4.3)Deterministic PDA

 

 

 

 

Deterministic Push-Dow  n

Automata: A PDA is said to be deterministic if all the derivations in the design have to give only a single move.

The below diagram shows an example for Nondeterministic push-down automata.

NDPDA

On the state q0, if the input symbol is a and the stack top symbol is a, we are moving to two states.

We do some practice examples to write deterministic push-down automata.

Example 1:

Take the language L = {a^nb^2n where n > 0}

The strings in the language are L = {abb, aabbbb, . . . }

·       The language has a’s followed by b’s.

·       If we have a single a, we have two b’s. It means multiples of 2.

·       The logic is simple.

·       Whenever we see an input symbol ‘a’, we push it onto the stack.

·       We need to pop the stack symbol a for every second occurrence of b.

·       The below diagram shows the DPDA for the language L.

DPDA for L

·       On the state q0, if the input symbol is a and the stack top is z, or a. we push onto the stack.

·       On the state q0, if we see the input symbol b, we are moving to state q1 and doing no operation.

·       We have seen the first input symbol b. to change the logic. We move to state q1.

·       On state q1, if we see the input symbol b, we pop the element from the stack because we have seen the second b.

·       We move to state q2. and loop on to state q1 for every second occurrence of b.

·       On the state q2, if the input symbol is epsilon, move to the final state.

Example 2:

Take the language L1 = {wcw^R where w = (0+1)*}

The input alphabet Σ = {0,1,c}.

w^R shows the reverse of the w.

·       The strings in the language are L1 = {011c110, 001c100, . . . }

·       The reverse of 011 is 110. After the symbol c, we need to have the reverse of w.

·       The logic is simple. whatever we find before the symbol c we need to push onto the stack

·       After the symbol c, the first input should match the stack top. Because we need reverse of w.

·       After the symbol c, if the input symbol and stack top are the same, we do the pop operation.

·       The language L1 will accept single c also. Because w can take epsilon.

·       The below diagram shows the DPDA for the language L1.

DPDA for L1

·       On the state q0, whatever we see, we need to push on to the stack.

·       On the state q0. If the input is c, move to state q1. Because from now we need to check for reverse

·       on the state q1 if the input symbol and the stack symbol are the same pop the element.

·       On the state q1, if the input is epsilon and the stack top is z, we move to the final state.

4.4)Equivalence of CFG and PDA & Conversion

  CFG → PDA: Replace stack top with productions & match input.

  PDA → CFG: Use variables $A_{pq}$Apq​ and simulate push/pop behavior.

 

Equivalence of CFG and PDA (Part 1)

CFG TO PDA:

CFG TO PDA:

 

 

 

 

 

 

 

 

 

CFG to PDA Conversion :

Solution:

4.5)Pumping lemma for CFL

 

Example

Find out whether L={xⁿyn^zn|n>=1} is context free or not

Solution

·      Let L be context free.

·      L must satisfy pumping length, say n.

^·             Now we can take a string such that s=xⁿyⁿzⁿ

·      We divide s into 5 strings uvxyz.

Let n=4 so, s=x⁴y⁴z⁴

Case 1:

v and y each contain only one type of symbol.

{we are considering only v and y because v and y has power uv²xy²z}

X xx x yyyyz z zz

=uv^kxy^kz when k=2

=uv²xy²z

=xxxxxxyyyyzzzzz

=x⁶y⁴z⁵

(Number of x # number of y #number of z)

Therefore,The resultant string is not satisfying the condition

x⁶y⁴z⁵ ∉ L

If one case fails then no need to check another condition.

What is the pumping lemma for regular language?

There are two Pumping Lemmas (PL), which are defined for Regular Languages and Context - Free Languages.

Pumping lemma for Regular languages

Theorem:

Steps to prove that a language is not regular by using PLare as follows−

 

·      It gives a method for pumping (generating) many substrings from a given string.

·      In other words, we say it provides means to break a given long input string into several substrings.

·      Lt gives necessary condition(s) to prove a set of strings is not regular.

Theorem

For any regular language L, there exists an integer P, such that for all w in L

|w|>=P

We can break w into three strings, w=xyz such that.

(1)lxyl < P

(2)lyl > 1

(3)for all k>= 0: the string xy^kz is also in L

Application of pumping lemma

Pumping lemma is to be applied to show that certain languages are not regular.

It should never be used to show a language is regular.

·      If L is regular, it satisfies the Pumping lemma.

·      If L does not satisfy the Pumping Lemma, it is not regular.

 

4.6)INTERSECTIONS AND COMPLEMENTS OF CFL

• We proved that the union, product, and Kleene star closure of context-free languages are also context-free. This left open the question of intersection and complement.
  
  

THEOREM : 

• The intersection of two context-free languages may or may not be contextfree.
  
  
• All regular languages are context-free (Theorem 19). The intersection of two regular languages is regular (Theorem 12). Therefore, if L, and L2 are regular and context-free then
  
  
• L₁ ∩ L₂ is both regular and context-free.

 

• Let L₁ = {aⁿbⁿa^m, where n, m = 1 2 3 ... but n is not necessarily the same as m} = {aba abaa aabba ... }

 

• To prove that this language is context-free, we present a CFG that generates it.

 

• S → XA
  X → aXb | ab
  A → aA | a

• We could alternately have concluded that this language is context-free by observing that it is the product of the CFL {aⁿbⁿ} and the regular language aa*

• Let L₂ = {aⁿbⁿa^m, where n, m = 1 2 3 but n is not necessarily the same as m} = {aba aaba abbaa . . . }

• Be careful to notice that these two languages are different. To prove that this language is context-free, we present a CFG that generates it:

• S → AX
  X → aXb | ab
  A → aA | a

• Alternately we could observe that L, is the product of the regular language aa* and the CFL {bⁿaⁿ}.

• Both languages are context-free, but their intersection is the language L₃ = L₁ ∩ L₂ = {aⁿbⁿaⁿ for n = 1 2 3 . . .}

• since any word in both languages has as many starting a's as middle b's (to be in L₁) and as many middle-b's as final a's (to be in L₂).

• But we proved that this language L₃ is non-context-free. Therefore, the intersection of two context-free languages can be non-contextfree.

 

EXAMPLE

If L₁ and L₂ are two CFL's and if L₁ is contained in L₂, then the intersection is L₁ again, which is still context-free, for example,

• L₁ = {aⁿ for n = 1 2 3 ...}

• L₂ = PALINDROME

• L₁ is contained in L₂; therefore, L₁ ∩ L₂ = L₁

• which is context-free.

• Notice that in this example we do not have the intersection of two regular languages since PALINDROME is nonregular.

 

EXAMPLE

Let: L₁ = PALINDROME L₂ = language of a⁺b⁺a⁺ = language of aa*bb*aa*

• In this case, L₁ ∩ L₂ is the language of all words with as many final a's as initial a's with only b's in between.

• L₁ ∩ L₂ = {aⁿb^maⁿ n,m = 1 2 3 ... where n is not necessarily equal to m} = {aba abba aabaa aabbaa ... }

• This language is still context-free since it can be generated by this grammar:

• S → aSa | aBa
  B → bB | b

• or accepted by this PDA:

• 
• First, all the front a's are put into the STACK. Then the b's are ignored. Then we alternately READ and POP a's till both the INPUT TAPE and STACK run out simultaneously.

Again note that these languages are not both regular (one is, one is not).

 

EXAMPLE

Let L₁ be the language

• EQUAL = all words with the same number of a's and b's

• We know this language is context-free because we have seen a grammar that generates it:

• S → bA | aB
  A → bAA | aS | a
  B → aBB | bS | b

• Let L₂ be the language L₂ = {aⁿb^maⁿ n,m = 1 2 3... n = m or n ≠ m}

• The language L₂ was shown to be context-free in the previous example. Now: L₃ = L₁ ∩ L₂ = {aⁿb²ⁿaⁿ for n = 1 2 3 ... } = {abba aabbbbaa ...

• To be in L₁ = EQUAL, the b-total must equal the a-total, so there are 2n b's in the middle if there are n a's in the front and in the back.

• We use the Pumping Lemma to prove that this language is non-context-free.

• As always, we observe that the sections of the word that get repeated cannot contain the substrings ab or ba, since all words in L₃ have exactly one of each substring.

• This means that the two repeated sections (the v-part and ypart) are each a clump of one solid letter. If we write some word w of L₃ as : w=uvxyz

• then we can say of v and y that they are either all a's or all b's or one is A. However, if one is solid a's, that means that to remain a word of the form aⁿb^maⁿ the other must also be solid a's since the front and back a's must remain equal.

• But then we would be increasing both clumps of a's without increasing the b's, and the word would then not be in EQUAL.

• If neither v nor y have a's, then they increase the b's without the a's and again the word fails to be in EQUAL.

• Therefore, the Pumping Lemma cannot apply to L₃, so L₃ is non-contextfree.

 

THEOREM : The complement of a context-free language may or may not be context-free.

 

• If L is regular, then L' is also regular and both are context-free.

 

• This is one of our few proofs by indirect argument.
• Suppose the complement of every context-free language were context-free.

 

• Then if we started with two such languages, L₁ and L₂, we would know that L₁' and L₂' are also context-free. Furthermore, L₁' + L₂' would have to be context free.

 

• Not only that but, (L₁' + L₂')' would also have to be context-free, as the complement of a context-free language.

• But, (L₁' + L₂')' = L₁ ∩ L₂ and so the intersection of L₁ and L₂ must be context-free.

• But L₁ and L₂ are any arbitrary CFL's, and therefore all intersections of context-free languages would have to be context-free.

• But by the previous theorem we know that this is not the case. Therefore, not all context-free languages have context-free complements.

 

EXAMPLE

• All regular languages have been covered in the proof above. There are also some nonregular but context-free languages that have context-free complements.

• One example is the language of palindromes with an X in the center, PALINDROMEX. This is a language over the alphabet {a, b, X}.

• = {w X reverse(w), where w is any string in (a + b)*} = {X aXa bXb aaXaa abXba baXab bbXbb . . . }

• This language can be accepted by a deterministic PDA such as the one below:

• 

• Since this is a deterministic machine, every input string determines some path from START to a halt state, either ACCEPT or REJECT.

• We have drawn in all possible branching edges so that no input crashes.

• The strings not accepted all go to REJECT. In every loop there is a READ statement that requires a fresh letter of input so that no input string can loop forever.

• (This is an important observation, although there are other ways to guarantee no infinite looping.)

• To construct a machine that accepts exactly those input strings that this machine rejects, all we need to do is reverse the status of the halt states from ACCEPT to REJECT and vice versa.

• This is the same trick we pulled on FA's to find machines for the complement language.

• In this case, the language L' of all input strings over the alphabet Σ = {a, b, X} that are not in L is simply the language accepted by:

• 

• We may wonder why this trick cannot be used to prove that the complement of any context-free language is context-free, since they all can be defined by PDA's. The answer is nondeterminism.

• If we have a nondeterministic PDA then the technique of reversing the status of the halt states fails.

• Remember that when we work with nondeterministic machines we say that any word that has some path to ACCEPT is in the language of that machine.

• In a nondeterministic PDA a word may have two possible paths, the first of which leads to ACCEPT and the second of which leads to REJECT.

• We accept this word since there is at least one way it can be accepted. Now if we reverse the status of each halt state we still have two paths for this word: the first now leads to REJECT and the second now leads to ACCEPT.

• Again we have to accept this word since at least one path leads to ACCEPT.

• The same word cannot be in both a language and its complement, so the halt-status-reversed PDA does not define the complement language.

• Let us be more concrete about this point. The following (nondeterministic) PDA accepts the language NON NULL EVEN PALINDROME:

• 

• We have drawn this machine so that, except for the nondeterminism at the first READ, the machine offers no choice of path, and every alternative is labeled. All input strings lead to ACCEPT or REJECT, none crash or loop forever.

• Let us reverse the status of the halt states to create this PDA

• 

• The word abba can be accepted by both machines. To see how it is accepted by the first PDA, we trace its path.

• 

• To see how it can be accepted by the second PDA we trace this path:

• 

• There are many more paths this word can take in the second PDA that also lead to acceptance. Therefore halt-state reversal does not always change a PDA for L into a PDA for L'

 

 

 

 

 

 

 

 

 

 

 

 

4.7)Non CFL