Context-free Grammars & Push-Down Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Closure Properties of Context Free Languages

Context Free languages are accepted by pushdown automata but not by finite automata. Context free languages can be generated by context free grammar which has the form :

A -> ρ (where A ∈ N and ρ ∈ (T ∪ N)* and N is a non-terminal and T is a terminal)
 
Properties of Context Free Languages

Union : If L1 and If L2 are two context free languages, their union L1 ∪ L2 will also be context free. For example,
L1 = { aⁿbⁿc^m | m >= 0 and n >= 0 } and L2 = { aⁿb^mc^m | n >= 0 and m >= 0 }
L3 = L1 ∪ L2 = { aⁿbⁿc^m ∪ aⁿb^mc^m | n >= 0, m >= 0 } is also context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.
 
Concatenation : If L1 and If L2 are two context free languages, their concatenation L1.L2 will also be context free. For example,
L1 = { aⁿbⁿ | n >= 0 } and L2 = { c^md^m | m >= 0 }
L3 = L1.L2 = { aⁿbⁿc^md^m | m >= 0 and n >= 0} is also context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of c’s should be equal to number of d’s. Their concatenation says first number of a’s should be equal to number of b’s, then number of c’s should be equal to number of d’s. So, we can create a PDA which will first push for a’s, pop for b’s, push for c’s then pop for d’s. So it can be accepted by pushdown automata, hence context free.
 
Kleene Closure : If L1 is context free, its Kleene closure L1* will also be context free. For example,
L1 = { aⁿbⁿ | n >= 0 }
L1* = { aⁿbⁿ | n >= 0 }* is also context free.
 
Intersection and complementation : If L1 and If L2 are two context free languages, their intersection L1 ∩ L2 need not be context free. For example,
L1 = { aⁿbⁿc^m | n >= 0 and m >= 0 } and L2 = (a^mbⁿcⁿ | n >= 0 and m >= 0 }
L3 = L1 ∩ L2 = { aⁿbⁿcⁿ | n >= 0 } need not be context free.
L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their intersection says both conditions need to be true, but push down automata can compare only two. So it cannot be accepted by pushdown automata, hence not context free.
Similarly, complementation of context free language L1 which is ∑* – L1, need not be context free.
 
Deterministic Context-free Languages

Deterministic CFL are subset of CFL which can be recognized by Deterministic PDA. Deterministic PDA has only one move from a given state and input symbol. For example, L1= { aⁿbⁿc^m | m >= 0 and n >= 0} is a DCFL because for a’s, we can push on stack and for b’s we can pop. It can be recognized by Deterministic PDA. On the other hand, L3 = { aⁿbⁿc^m ∪ aⁿb^mc^m | n >= 0, m >= 0 } cannot be recognized by DPDA because either number of a’s and b’s can be equal or either number of b’s and c’s can be equal. So, it can only be implemented by NPDA. Thus, it is CFL but not DCFL.
Note : Out of union, concatenation, complementation, intersection and kleene-closure, DCFL are closed only under complementation.

Question : Consider the language L1,L2,L3 as given below.
L1 = { a^mbⁿ | m, n >= 0 }
L2 = { aⁿbⁿ | n >= 0 }
L3 = { aⁿbⁿcⁿ | n >= 0 }
Which of the following statements is NOT TRUE?
A. Push Down Automata (PDA) can be used to recognize L1 and L2
B. L1 is a regular language
C. All the three languages are context free
D. Turing machine can be used to recognize all the three languages

Solution : Option (A) says PDA can be used to recognize L1 and L2. L1 contains all strings with any no. of a followed by any no. of b. So, it can be accepted by PDA. L2 contains strings with n no. of a’s followed by n no. of b’s. It can also be accepted by PDA. So, option (A) is correct.
Option (B) says that L1 is regular. It is true as regular expression for L1 is a*b*.
Option (C) says L1, L2 and L3 are context free. L3 languages contains all strings with n no. of a’s followed by n no. of b’s followed by n no. of c’s. But it can’t be accepted by PDA. So option ( C) is not correct.
Option (D) is correct as Turing machine can be used to recognize all the three languages.

Question : The language L = { 0ⁱ12ⁱ | i ≥ 0 } over the alphabet {0, 1, 2} is :
A. Not recursive
B. Is recursive and deterministic CFL
C. Is regular
D. Is CFL bot not deterministic CFL.

Solution : The above language is deterministic CFL as for 0’s, we can push 0 on stack and for 2’s we can pop corresponding 0’s. As there is no ambiguity which moves to take, it is deterministic. So, correct option is (B). As CFL is subset of recursive, it is recursive as well.
 
Question : Consider the following languages:
L1 = { 0ⁿ1ⁿ| n≥0 }
L2 = { wcwr | w ɛ {a,b}* }
L3 = { wwr | w ɛ {a,b}* }
Which of these languages are deterministic context-free languages?
A. None of the languages
B. Only L1
C. Only L1 and L2
D. All three languages

Solution : Languages L1 contains all strings in which n 0’s are followed by n 1’s. Deterministic PDA can be constructed to accept L1. For 0’s we can push it on stack and for 1’s, we can pop from stack. Hence, it is DCFL.
L2 contains all strings of form wcwr where w is a string of a’s and b’s and wr is reverse of w. For example, aabbcbbaa. To accept this language, we can construct PDA which will push all symbols on stack before c. After c, if symbol on input string matches with symbol on stack, it is popped. So, L2 can also be accepted with deterministic PDA, hence it is also DCFL.
L3 contains all strings of form wwr where w is a string of a’s and b’s and wr is reverse of w. But we don’t know where w ends and wr starts. e.g.; aabbaa is a string corresponding to L3. For first a, we will push it on stack. Next a can be either part of w or wr where w=a. So, there can be multiple moves from a state on an input symbol. So, only non-deterministic PDA can be used to accept this type of language. Hence, it is NCFL not DCFL.
So, correct option is (C). Only, L1 and L2 are DCFL.

Question : Which one of the following grammars generate the language L = { aⁱb^j | i ≠ j }
S -> AC | CB, C -> aCb | a | b, A -> aA | ɛ, B -> Bb | ɛ
S -> aS | Sb | a | b
S -> AC | CB, C -> aCb | ɛ, A -> aA | ɛ, B -> Bb | ɛ
S -> AC | CB, C -> aCb | ɛ, A -> aA | a, B -> Bb | b

Solution : The best way to solve these type of questions is to eliminate options which do not satisfy conditions. The conditions for language L is no. of a’s and no. of b’s should be unequal.
In option (B), S => aS => ab. It can generate strings with equal a’s and b’s. So, this option is incorrect.
In option (C), S => AC => C => ɛ. In ɛ, a’s and b’s are equal (0), so it is not correct option.
In option (A), S will be replaced by either AC or CB. C will either generate no. of a’s more than no. of b’s by 1 or no. of b’s more than no. of a’s by 1. But one more a or one more b can be compensated by B -> bB | ɛ or A -> aA | ɛ respectively. So it may give strings with equal no. of a’s and b’s. So, it is not a correct option.
In option (D), S will be replaced by either AC or CB. C will always generate equal no. of a’s and b’s. If we replace S by AC, A with add atleast one extra a. and if we replace S by CB, B will add atleast one extra b. So this grammar will never generate equal no. of a’s and b’s. So, option (D) is correct.

Decidability

Identifying languages (or problems*) as decidable, undecidable or partially decidable is a very common question in GATE. With correct knowledge and ample experience, this question becomes very easy to solve.

Lets start with some definitions:-

Recursive language(REC) – A language ‘L’ is said to be recursive if there exists a Turing machine which will accept all the strings in ‘L’ and reject all the strings not in ‘L’. The Turing machine will halt every time and give an answer(accepted or rejected) for each and every string input.

Recursively enumerable language(RE) – A language ‘L’ is said to be a recursively enumerable language if there exists a Turing machine which will accept (and therefore halt) for all the input strings which are in ‘L’ but may or may not halt for all input strings which are not in ‘L’. By definition , all REC languages are also RE languages but not all RE languages are REC languages.

Decidable language – A language ‘L’ is decidable if it is a recursive language. All decidable languages are recursive languages and vice-versa.

Partially decidable language – A language ‘L’ is partially decidable if ‘L’ is a RE language.

Undecidable language – A language is undecidable if it is not decidable. An undecidable language maybe a partially decidable language or something else but not decidable. If a language is not even partially decidable , then there exists no Turing machine for that language.
Now lets solve some examples –

One way to solve decidability problems is by trying to reduce an already known undecidable problem to the given problem. By reducing a problem P1 to P2, we mean that we are trying to solve P1 by using the algorithm used to solve P2.

If we can reduce an already known undecidable problem P1 to a given problem P2 , then we can surely say that P2 is also undecidable. If P2 was decidable, then P1 would also be decidable but that becomes a contradiction because P1 is known to be undecidable.

For eg.

1. Given a Turing machine ‘M’, we need to find out whether a state ‘Q’ is ever reached when a string ‘w’ is entered in ‘M’. This problem is also known as the ‘State Entry problem’.

Now lets try to reduce the Halting problem to the State Entry problem. A Turing machine only halts when a transition function δ (qi , a) is not defined. Change every undefined function δ(qi,a) to δ(qi,a) = (Q, a, L or R). Note that the state Q can only be reached when the Turing machine halts.

Suppose we have have an algorithm for solving the State Entry problem which will halt every time and tell us whether state Q can be reached or not. By telling us that we can or cannot reach state Q every time, it is telling us that the Turing machine will or will not halt, every time. But we know that is not possible because the halting problem is undecidable. That means that our assumption that there exists an algorithm which solves the State Entry problem and halts and gives us an answer every time, is false. Hence, the state entry problem is undecidable.

2. Given two regular languages L1 and L2, is the problem of finding whether a string ‘w’ exists in both L1 and L2, a decidable problem or not.

First we make two Turing machines TM1 and TM2 which simulate the DFAs of languages L1 and L2 respectively. We know that a DFA always halts, so a Turing machine simulating a DFA will also always halt. We enter the string ‘w’ in TM1 and TM2. Both Turing machines will halt and give us an answer. We can connect the outputs of the Turing machines to a modified ‘AND’ gate which will output ‘yes’ only when both the Turing machines answer ‘yes’. Otherwise it will output ‘no’.

Since this system of two Turing machines and a modified AND gate will always stop, this problem is a decidable problem.

There are a lot of questions on this topic. There is no universal algorithm to solve them. Most of the questions require unique and ingenious proofs. Here is where experience is needed. By solving a lot of these problems, one can become very quick in coming up with proofs for these problems on the spot. So, keep practicing.

*The words ‘language’ and ‘problem’ can be used synonymously in Theory of computation. For eg. The ‘Halting problem’ can also be written as ‘L = {<M, w> | Turing machine ‘M’ halts on input ‘w’}’. Here ‘L’ is a language.