GATE Computer Science Engineering(CSE) 2027 Test: Theory of Computation

LL(1) Grammar: The first 'L' refers to scanning of input from Left to Right, the second 'L' refers to producing the Leftmost Derivation and the (1) stands for using only 1 lookahead input symbol at each step to make parsing action decisions. Hence, a context-free grammar G = (VT, VN, S, P) whose parsing table has no multiple entries is said to be LL(1) Grammar.
LL(1) Conflicts:

• Checking whether a grammar is ambiguous or not is undecidable.
• A grammar can be LL(1) only if it is not ambiguous, not left recursive and it must not contain left factoring and vice-versa is not necessary.
• Any regular language can be LL(1) is true statement since we can write regular grammar which follows the above conflict.

Since a grammar is LL(1) only if it does not contain left recursion, ambiguity and left factoring, hence, to convert an arbitrary CFG to LL(1), all the three should be eliminated

Pumping Lemma for Regular Languages: For any regular language L, if a string 'v' is pumped any number of times, it will still belong to the same language.
If L is a regular language, there exists an integer 'n' in which if all x∈L with |x|≥n, then there exists u,v,w∈Σ∗ such that x=uvw and it further follows the following conditions:

Pumping Lemma for Context-Free Languages: For any context-free language L, there exist two substrings that can be pumped any number of times and that string will still be following the same grammar.
If L is a context-free language, there exists an integer 'n' in which all x∈L with |x|≥n and there exists u,v,w,x,y∈Σ∗ such that x=uvwxy and it further follows the following conditions:

Recursive Languages: Recursive Languages do not follow the pumping lemma.

Recursively Enumerable Languages: Recursively Enumerable Languages do not follow the pumping lemma.

S → aS | bS | ϵ 

This grammar results in (a + b)*

DFA for this grammar is:

Diagram

Now, consider the options one by one:

Option 1:

{aⁿb^m | n, m ≥ 0}

Here order is fixed, means first any number of a will come then any number of b. It is incorrect.

Option 2: 

{w ϵ {a, b} * | w has an equal number of a’s and b’s}

As given grammar is not generating the expression which generates only equal number of a and b. So,

not correct.

Option 3:

{aⁿ | n ≥ 0} {bⁿ | n ≥ 0} {aⁿbⁿ | n ≥ 0}

Here, also order is fixed. So, it is incorrect.

Option 4:

{a, b}*

This is equivalent to (a + b)*. So, it is correct.

Grammar:

S → XY

X → aX | a

Y → aYb | ϵ

Explanation:

X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}

a^mbⁿ, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.

Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.

Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect

The smallest length string generated by Y is ϵ. In a^mbⁿ, n ≥ 0 and hence option 4 is incorrect.

{ a, aab, aaabb,………….} which is equivalent to :

L = {a^mbⁿ | m > n, n ≥ 0}

Suppose grammar G1:

S₁ → aS₁b|ϵ

It generates language in which number of a’s are equal to number of b’s and all a’s are followed by b’s

L₁ = { aⁿ bⁿ | n ≥ 0}.

It is deterministic context free language. Extra memory is required for this. So, it can’t be accepted by finite state automata. L₁ is not a regular language.

Now, another grammar let G2: S₂ → abS₂|ϵ

This grammar also generates language in which number of a’s are equal to number of b’s. But it generates language L₂ = { (ab)ⁿ | n ≥ 0 }

Regular expression for this = (ab)*

It doesn’t require any extra memory to remember the last string. It can be accepted by finite state automata. So, L₂ is regular.

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {aⁿ |n ≥ 0} ∪ {aⁿbⁿ| n ≥ 0}

{aⁿ |n ≥ 0} is a regular language and {aⁿbⁿ| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from aⁿ or from aⁿbⁿ. Both have a common prefix.

Statement I: FALSE

If L₁ ∪ L₂ is regular, then neither L₁ nor L₂ needs necessarily be regular.

Example:

Assume L₁= {aⁿ bⁿ, n ≥ 0} over the alphabet {a, b} and L₂ be the complement of L₁.

Neither L₁ nor L₂ is regular (both are DCFL) but L₁ ∪ L₂= {aⁿ bⁿ} ∪ {aⁿ bⁿ}^c = (a + b)^* is regular.

Statement II: FALSE. The infinite Union of regular languages is not regular.

Example:

Given alphabet {a, b}.

L₁= {ε}

L₂= {ab}

L₃= {aabb}

L₄= {aaabbb}

:

:

L = L₁ ∪ L₂ ∪ L₃ ∪ L₄ …

Each of the above are regular but their infinite Union gives L₁= {aⁿ bⁿ, n ≥ 0} which is not regular but DCFL.

Note:

DCFL → Deterministic context free language

Regular language L = {x|x = a^2+3k or x = b^10+12k k ≥ 0}.

L = {a², a⁵, a⁸, a¹¹ … ∪ b¹⁰, b²², b³⁴…}

Pumping Lemma:

Let L be an infinite regular language. Then there exists some positive integer m such that any w ϵ L with |w|≥ m can be decomposed as

w = xyz

with |xy|≤ m such that w_i = xyⁱz

is also L for all i = 0, 1, 2, …

Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b¹⁰) does not repeat anything, but string with length 11 (i.e., w = b¹¹) will repeat states.

Hence option 1, 2, and 3 are eliminated.

Therefore 24 can be the pumping lemma length.

A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.

Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.