Context-free Grammars & Push-Down Automata

Closure Properties of Context-Free Languages

Context-free languages (CFLs) are languages generated by context-free grammars (CFGs) or equivalently accepted by push-down automata (PDA). A CFG has productions of the form A → ρ where A is a non-terminal (A ∈ N) and ρ is a string from (T ∪ N)* (terminals ∪ non-terminals).

Basic closure properties

• Union (L1 ∪ L2) - If L1 and L2 are CFLs, then their union is a CFL. Example: L1 = { aⁿbⁿc^m | m ≥ 0, n ≥ 0 } and L2 = { aⁿb^mc^m | n ≥ 0, m ≥ 0 }. L3 = L1 ∪ L2 = { aⁿbⁿc^m ∪ aⁿb^mc^m | n ≥ 0, m ≥ 0 } is context-free. Construction idea for grammars: given grammars G1 and G2 with start symbols S1 and S2, a grammar for the union has a new start S with S → S1 | S2. Construction idea for PDAs: an NPDA can nondeterministically choose which PDA to simulate (simulate P1 or P2).
• Concatenation (L1·L2) - If L1 and L2 are CFLs then L1·L2 is a CFL. Example: L1 = { aⁿbⁿ | n ≥ 0 } and L2 = { c^md^m | m ≥ 0 }. L3 = L1·L2 = { aⁿbⁿc^md^m | n ≥ 0, m ≥ 0 } is context-free. Construction idea for grammars: given start symbols S1 and S2, use S → S1 S2. Construction idea for PDAs: use nondeterminism (or stack-content markers) to accept first part, then continue for second part.
• Kleene closure (L*) - If L is a CFL then L* is a CFL. Example: if L = { aⁿbⁿ | n ≥ 0 } then L* is context-free. Construction idea for grammars: with start symbol S of original grammar, add S' → S S' | ε where S' is the new start symbol to generate any number of concatenated copies.
• Intersection and complementation - CFLs are not closed under intersection or complementation in general. Counterexample for intersection: L1 = { aⁿbⁿc^m | n ≥ 0, m ≥ 0 } and L2 = { a^mbⁿcⁿ | n ≥ 0, m ≥ 0 }. L1 ∩ L2 = { aⁿbⁿcⁿ | n ≥ 0 } which is not context-free. Reason: a PDA has a single stack and can compare only two quantities reliably; requiring equality of three counts generally exceeds CFL power. Complementation: since CFLs are not closed under intersection and using De Morgan laws, complementation need not produce a CFL.

Important additional facts

• Every CFL is closed under substitution, homomorphism and inverse homomorphism (standard results in formal language theory).
• Every CFL is closed under intersection with a regular language. This is often used to filter strings of interest using a DFA combined with a PDA.

Deterministic Context-Free Languages (DCFL)

Deterministic CFLs (DCFLs) are those recognised by a deterministic push-down automaton (DPDA). A DPDA has at most one transition possible from a given state with a given input symbol and top-of-stack symbol (no nondeterministic choices).

Key points about DCFLs:

• DCFLs ⊂ CFLs. Every DCFL is a CFL but not every CFL is a DCFL.
• DCFLs are closed under complement. This is a notable difference from general CFLs.
• DCFLs are not closed under union, concatenation or Kleene star in general.
• DCFLs (like CFLs) are closed under intersection with regular languages.

Examples from the earlier section:

• L1 = { aⁿbⁿc^m | m ≥ 0, n ≥ 0 } is a DCFL. Intuition: DPDA can push for each a, pop for each b, and ignore or handle the trailing c's deterministically.
• L3 = L1 ∪ L2 where L2 = { aⁿb^mc^m } is a CFL but not necessarily a DCFL. Reason: at the point after reading b's, a deterministic machine cannot always decide whether to expect matching b's or matching c's without lookahead or nondeterminism; NPDA is required.

Practical constructions

• To build a PDA for L = { aⁿbⁿ | n ≥ 0 } use the stack to push an A for each a and pop one for each b; accept when input is exhausted and stack is empty.
• To accept concatenations or Kleene star, allow the PDA to nondeterministically choose boundaries between components and reset stack behaviour appropriately.

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 number of a followed by any number of b. So, it can be accepted by PDA. L2 contains strings with n number of a's followed by n number 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 number of a's followed by n number of b's followed by n number 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 : Language 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 number of a's more than number of b's by 1 or number of b's more than number 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 number 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 number of a's and b's. If we replace S by AC, A will add at least one extra a and if we replace S by CB, B will add at least one extra b. So this grammar will never generate equal number of a's and b's. So, option (D) is correct.

Decidability

Determining whether languages (or decision problems) are decidable, partially decidable (recursively enumerable), or undecidable is a central topic in computability theory. The following definitions are standard and used frequently.

• Recursive language (REC) - A language L is recursive if there exists a Turing machine that halts on every input and accepts exactly the strings in L and rejects exactly those not in L. The Turing machine always gives a definite answer (halt and accept or halt and reject).
• Recursively enumerable language (RE) - A language L is recursively enumerable if there exists a Turing machine that accepts every string in L (and halts on those inputs), but for strings not in L the machine may either reject or loop forever. Every recursive language is recursively enumerable, but not every RE language is recursive.
• Decidable language - synonymous with recursive: the language is decidable if there is a Turing machine that always halts and correctly answers membership for every input.
• Partially decidable language - synonymous with recursively enumerable: there is a Turing machine that accepts members but may not halt on non-members.
• Undecidable language - a language is undecidable if it is not decidable. An undecidable language might still be RE (partially decidable) or not RE at all.

Method: reductions

A standard method to show undecidability of a problem P2 is to reduce a known undecidable problem P1 to P2. If you can show that solving P2 (with a hypothetical decider) would allow you to solve P1, then P2 must also be undecidable. The halting problem is the canonical undecidable problem frequently used for reductions.

Example 1 - State Entry Problem

Problem statement - Given a Turing machine M and an input w, determine whether a particular state Q of M is ever reached during the computation on w.

Reduction idea from the Halting problem

Modify the machine M so that every originally undefined transition (which would have caused halting) is instead redirected to move to a new distinguished state Q. Then Q is reached if and only if the original machine would have halted.

If there were a decider for the State Entry problem that always halts and answers whether Q is reachable from the configuration on input w, then using the above transformation we could decide the Halting problem. Since the Halting problem is undecidable, the State Entry problem must also be undecidable.

Example 2 - Intersection membership for regular languages

Problem statement - Given two regular languages L1 and L2, decide whether there exists a string w that is in both L1 and L2.

Reasoning

Because regular languages are represented by DFAs, construct Turing machines TM1 and TM2 that simulate the DFAs for L1 and L2 respectively. Each TM will always halt on any input because DFAs always halt. To decide whether there exists some w ∈ L1 ∩ L2, we can algorithmically enumerate all strings (in some standard order) and simulate TM1 and TM2 on each string; whenever both accept, output "yes". This procedure will halt iff such a string exists. Alternatively, form the product DFA for intersection and check its language for emptiness; emptiness for regular languages is decidable. Therefore the problem is decidable.

Remarks and exam tips

• Practice proving closure or non-closure by explicit construction (for closure) or by counterexamples/reductions (for non-closure).
• For decidability questions, think of known decidable/undecidable problems and whether a reduction is plausible. Common sources of undecidability in proofs are the Halting problem, Post's Correspondence Problem, and membership/emptiness for Turing-machine-defined languages.
• Remember standard equivalences: DFAs ⇔ regular languages, CFGs ⇔ PDAs ⇔ CFLs, and Turing machines ⇔ recursively enumerable sets.

Concluding summary

Context-free languages have useful closure properties: they are closed under union, concatenation, Kleene star and intersection with regular sets, but not under arbitrary intersection or complementation. Deterministic CFLs form a strict subclass that is closed under complementation but not under many other operations. Decidability questions are settled by constructive algorithms when they exist or by reductions to/from known undecidable problems when they do not. Regular practice with constructions and reductions develops the intuition and speed required to handle typical examination problems in theory of computation.