Context-Free-Language

Question 1

Which one of the following languages over Σ = {a,b} is NOT context-free?

A
{wwR |w ∈ {a,b}*}
B
{wanwRbn |w ∈ {a,b}*, n ≥ 0}
C
{anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
D
{wanbnwR |w ∈ {a,b}*, n ≥ 0}
       Theory-of-Computation       Context-Free-Language       GATE 2019       Video-Explanation
Question 1 Explanation: 
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
Question 2
Consider the following languages:
I. {am bn cp dq ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {am bn cp dq ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {am bn cp dq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {am bn cp dq ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are context-free?
A
I and IV only
B
I and II only
C
II and III only
D
II and IV only
       Theory-of-Computation       Context-Free-Language       GATE 2018       Video-Explanation
Question 2 Explanation: 
i) am bn cp dq | m+p = n+q,
m-n = q-p
First we will push a’s in the stack then we will pop a’s after watching b’s.
Then some of a’s might left in the stack.
Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s.
And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) am bn cp dq | m=n, p=q
Push a’s in stack. Pop a’s watching b’s.
Now push c’s in stack.
Pop c’s watching d’s.
So it is context free language.
iii) am bn cp dq | m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
Question 3
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G1: S → aSb|T, T → cT|ϵ
G2: S → bSa|T, T → cT|ϵ
The language L(G1) ∩ L(G2) is
A
Finite
B
Not finite but regular
C
Context-Free but not regular
D
Recursive but not context-free
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-1]       Video-Explanation
Question 3 Explanation: 
Strings generated by G1:
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G2:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G1) and L (G2) are:
{ϵ, c, cc, ccc…}
So, L (G1) ∩ L (G2) can be represented by regular expression: c*
Hence the language L (G1) ∩ L (G2) is “Not finite but regular”.
Question 4
Consider the following languages over the alphabet Σ = {a, b, c}.
Let L1 = {an bn cm│m,n ≥ 0} and L2 = {am bn cn│m,n ≥ 0}
Which of the following are context-free languages?
I. L1 ∪ L2
II. L1 ∩ L2
A
I only
B
II only
C
I and II
D
Neither I nor II
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-1]       Video-Explanation
Question 4 Explanation: 
Strings in L1 = {ϵ, c, cc, …., ab, aabb,…., abc, abcc,…, aabbc, aabbcc, aabbccc,..}
Strings in L2 = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L1 ∪ L2 ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L1 ∪ L2) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L1 ∪ L2) is CFL.
Strings in L1 ∩ L2 = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L1 ∩ L2) will have (number of a’s = number of b’s = number of c’s)
i.e., (L1 ∩ L2) = {anbncn | n ≥ 0} which is CSL.
Question 5

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

A
I, II and IV only
B
I and III only
C
II and IV only
D
I only
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-2]       Video-Explanation
Question 5 Explanation: 
Since CFL is closed under UNION so L1 ∪ L2 is CFL, is a true statement.
CFL is not closed under complementation.
So L1 compliment may or may not be CFL. Hence is Context free, is a false statement.
L1 – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L1 ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L1∩R is context free.
CFL is not closed under INTERSECTION, so L1 ∩ L2 may or may not be CFL and hence IVth is false.
Question 6
Consider the following languages:
L1= {ap│p is a prime number}
L2= {anbmc2m| n ≥ 0, m ≥ 0}
L3= {anbnc2n│ n ≥ 0}
L4= {anbn│ n ≥ 1}
Which of the following are CORRECT?
I. L1 is context-free but not regular.
II. L2 is not context-free.
III. L3 is not context-free but recursive.
IV. L4 is deterministic context-free.
A
I, II and IV only
B
II and III only
C
I and IV only
D
III and IV only
       Theory-of-Computation       Context-Free-Language       GATE 2017 [Set-2]       Video-Explanation
Question 6 Explanation: 
L1 = {ap│p is a prime number} is a context sensitive language. So I is false.
L2 = {an bm c2m│n ≥ 0, m ≥ 0} is a context free as we have to do only one comparison (between b’s and c’s) which can be done by using PDA, so L2 is Context free and II is true.
L3 = {an bn c2n│n≥0} is context sensitive.
The reason it has more than one comparison (at a time) as we have to compare number of a’s, b’s and c’s.
So this cannot be done using PDA. Hence III is CSL and every CSL is recursive, so III is True
L4 = {an bn│n ≥ 1} is Context free (as well as Deterministic context free).
We can define the transition of PDA in a deterministic manner.
In beginning push all a’s in stack and when b’s comes pop one “a” for one “b”.
If input and stack both are empty then accept.
Question 7
Consider the following languages:
L1 = {an bm cn+m: m,n ≥ 1}
L2= {an bn c2n: n ≥ 1}
Which one of the following is TRUE?
A
Both L1 and L2 are context-free.
B
L1 is context-free while L2 is not context-free.
C
L2 is context-free while L1 is not context-free.
D
Neither L1 nor L2 is context-free.
       Theory-of-Computation       Context-Free-Language       GATE 2016 [Set-2]       Video-Explanation
Question 7 Explanation: 
L1 can be recognized by PDA, we have to push a’s and b’s in stack and when c’s comes then pop every symbol from stack for each c’s.
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L2 can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1st comparison:
number of a’s = number of b’s
2nd comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.
Question 8

Which of the following languages are context-free?

    L1 = {ambnanbm ⎪ m, n ≥ 1}
    L2 = {ambnambn ⎪ m, n ≥ 1}
    L3 = {ambn ⎪ m = 2n + 1}
A
L1 and L2 only
B
L1 and L3 only
C
L2 and L3 only
D
L3 only
       Theory-of-Computation       Context-Free-Language       GATE 2015 [Set-3]
Question 8 Explanation: 
L1: First push all the a's in the stack then push all the b's in the stack. Now pop all the b's from the stack watching next no. of a's. And then pop all the a's from the stack watching next no. of b's. So can be done by PDA, hence CFL.
L2: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparison with the next b's. So not CFL.
L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Question 9

Consider the languages

    L1 = {0i1j | i != j}.
    L2 = {0i1j | i = j}.
    L3 = {0i1j | i = 2j+1}.
    L4 = {0i1j | i != 2j}.

Which one of the following statements is true?

A
Only L2 is context free
B
Only L2 and L3 are context free
C
Only L1 and L2 are context free
D
All are context free
       Theory-of-Computation       Context-Free-Language       GATE 2010
Question 9 Explanation: 
All languages viz L1, L2, L3 and L4 has only one comparison and it can be accepted by PDA (single stack), hence all are Context Free Languages.
Question 10
S→aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of

A
all palindromes.
B
all odd length palindromes.
C
strings that begin and end with the same symbol.
D
all even length palindromes.
       Theory-of-Computation       Context-Free-Language       GATE 2009
Question 10 Explanation: 
From the grammar, we can easily infer that it generates all the palindromes of odd length, for ex: strings {aba, bab, aaa, bbb, ….}
Question 11

Let L1 = {0n+m1n0m|n,m ≥ 0}, L2 = {0n+m1n+m0m|n,m ≥ 0}, and L3 = {0n+m1n+m0n+m|n,m ≥ 0}. Which of these languages are NOT context free?

A
L1 only
B
L3 only
C
L1 and L2
D
L2 and L3
       Theory-of-Computation       Context-Free-Language       GATE 2006
Question 11 Explanation: 
L1 can be accepted by PDA, we need to push all 0’s before 1’s and when 1’s comes in input string we need to pop every 0’s from stack for every 1’s and then for every 0’s. If stack and input string is empty at the same time then the string belongs to L1.
But for L2 and L3 PDA implementation is not possible. The reason is, in L2 there are two comparison at a time, first the number of 0’s in beginning should be equal to 1’s and then 0’s after 1’s must be less than or equal to number of 1’s. Suppose for initial 0’s and 1’s are matched by using stack then after matching stack will become empty and then we cannot determine the later 0’s are equal to or less than number of 1’s. Hence PDA implementation is not possible. Similarly L3 also has the similar reason.
Question 12

Consider the languages:

L1 = {anbncm |n,m > 0} and L2 = {anbmcm |n,m > 0}

Which one of the following statements is FALSE?

A
L1 ∩ L2 is a context-free language
B
L1 ∪ L2 is a context-free language
C
L1 and L2 are context-free languages
D
L1 ∩ L2 is a context sensitive language
       Theory-of-Computation       Context-Free-Language       GATE 2005
Question 12 Explanation: 
CFL is closed under Union.
CFL is not closed under Intersection.
L1 = {anbncm | n>0 & m>0}
L2 = {ambncn | n>0 & m>0}
L3 = L1 ∩ L2
={anbncn | n>0} It is not context-free.
Question 13

Consider the languages:

L1 = {wwR |w ∈ {0,1}*}
L2 = {w#wR | w ∈ {0,1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1)*}

Which one of the following is TRUE?

A
L1 is a deterministic CFL
B
L2 is a deterministic CFL
C
L3 is a CFL, but not a deterministic CFL
D
L3 is a deterministic CFL
       Theory-of-Computation       Context-Free-Language       GATE 2005
Question 13 Explanation: 
Given: L1 = {wwR | w ∈ {0,1}*}
→ Given L1 is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L2 = {w#wR | w ∈ (0,1)*}
→ Given L2 is CFL and also DCFL.
→ The string w and wR are separated by special symbol '#'.
→ L3 = {ww | w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L2 is DCFL. (✔️)
Question 14

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
       Theory-of-Computation       Context-Free-Language       GATE 1999
Question 14 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 15

Show that the language L = {xcx| x ∈ {0,1}* and c is a terminal symbol} is not context free, c is not 0 or 1.

A
Theory Explanation.
       Theory-of-Computation       Context-Free-Language       GATE 1999
Question 16

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

A
the set of all binary strings with unequal number of 0’s and 1’s
B
the set of all binary strings including the null string
C
the set of all binary strings with exactly one more 0’s than the number of 1’s or one more 1 than the number of 0’s
D
None of the above
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 16 Explanation: 
(B) is the answer. Because for any binary string of 0's and 1's we can append another string to make it contain equal no. of 0's and 1's, i.e., any string over {0,1} is a prefix of a string in L.
Question 17

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

A
the sentence
if a then if b then c:=d
B
the left most and right most derivations of the sentence
if a then if b then c:=d
give rise top different parse trees
C
the sentence
if a then if b then c:=d else c:=f
has more than two parse trees
D
the sentence
if a then if then c:=d else c:=f
has two parse trees
       Theory-of-Computation       Context-Free-Language       GATE 1996
Question 17 Explanation: 
We have to generate
"if a then if b then c:=d else c:=f".
Parse tree 1:

Parse tree 2:
Question 18

The intersection of two CFL's is also a CFL.

A
True
B
False
       Theory-of-Computation       Context-Free-Language       GATE 1987
Question 18 Explanation: 
Context free language is not closed under intersection.
Question 19
 For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR= 10110. Which of the following languages is/are context-free?
A
L={w x wR xR | w, x ∈ {0,1}* }
B
L={w wR x xR | w, x ∈ {0,1}* }
C
L={w x xR wR | w, x ∈ {0,1}* }
D
L={w x wR | w, x ∈ {0,1}* }
       Theory-of-Computation       Context-Free-Language       GATE 2021 CS-Set-2
Question 19 Explanation: 

Option A: L={w x wR  xR  | w, x ∈ {0,1}* }

This is not CFL as if we push “w” then “x” then we cannot match wR with “w” as top of stack contains x.

 

Option B: L={w wR x xR  | w, x ∈ {0,1}* }

This is CFL. We non deterministically guess the middle of the string. So we push “w” then match with wR  and again push x and match with xR  

 

Option C: L={w x  xR wR   | w, x ∈ {0,1}* } 

This is also CFL. We non deterministically guess the middle of the string. So we push “w” then push x and then  match with xR  and again match with wR 

 

Option D: L={w x  wR   | w, x ∈ {0,1}* }

This is a regular language (hence CFL). In this language every string start and end with same symbol (as x can expand).



Question 20
Let L1be a regular language and L2be a context-free language. Which of the following languages is/are context free
A
B
C
D
       Theory-of-Computation       Context-Free-Language       GATE 2021 CS-Set-2
Question 20 Explanation: 
Question 21
A
L 1 and L 2 are regular.
B
L 1 and L 2 are context-free.
C
L 1 is regular and L 2 is context-free.
D
L 1 and L 2 are context-free but not regular.
       Theory-of-Computation       Context-Free-Language       GATE 2022
Question 21 Explanation: 
Both L1 and L2 are regular.
Since no condition on the value of “n” is mentioned so for a particular case we can assume n=0, now when n=0 the language L1= w =(a+b)*
So if one case is (a+b)* then now even we assume any value of “n” the generated string will already present in (a+b)* thus L1=(a+b)*.
L2: In L2 the middle X can expand and consume all symbols of w except the first symbol and symbols of wr except the last symbol so L2 will be equivalent to language all strings start and end with the same symbol, hence L2 is regular.
Question 22
Consider the following languages:
A
L 1 is not context-free but L 2 and L 3 are deterministic context-free.
B
Neither L 1 nor L 2 is context-free.
C
D
Neither L 1 nor its complement is context-free.
       Theory-of-Computation       Context-Free-Language       GATE 2022
Question 22 Explanation: 
L1=ww is a well-known CSL (non-CFL) and its complement is CFL.
L2={an bn cm | m,n >=0} this contains only one comparison (number of a’s = number of b’s) so this is DCFL.
L3={am bn cn | m,n >=0} this contains only one comparison (number of b’s = number of c’s) so this is DCFL.
Intersection of L2 and L3 will have (number of a’s= number of b’s = number of c’s) i.e., {an bn cn | n >=0} so this is CSL (non-CFL).
So A is a true statement and rest all are false statements.
Question 23
A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A→ BC or A→ a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
A
2x – 1
B
2x
C
2x + 1
D
2x
       Theory-of-Computation       Context-Free-Language       ISRO-2018       Video-Explanation
Question 23 Explanation: 
Explanation:
→ For CNF, it is 2x - 1
→ For GNF, it is x
Question 24
Consider the grammar
S → ABCc ∣ bc
BA → AB
Bb → bb
Ab → ab
Aa → aa
Which of the following sentences can be derived by this grammar?
A
abc
B
aab
C
abcc
D
abbc
       Theory-of-Computation       Context-Free-Language       ISRO CS 2008
Question 24 Explanation: 
C is useless in S→ABCc so remove it.
S→ABc
Now see each of remaining production
Bb→bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
So
S→ABc→abc
Question 25
Consider the grammar with productions S → aSb | SS | ϵ This grammar is
A
not context-free, not linear
B
not context-free, linear
C
context-free, not linear
D
context-free, linear
       Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 25 Explanation: 
Linear grammar means regular grammar which is in the form of A→ Ba | b (or) A→ aB|b
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of non-terminals
It is clearly seen that given grammar is not linear but context-free.
Question 26
Let L = {ap| p is a prime}.
Then which of the following is true?
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free but accepted by a Turing Machine
       Theory-of-Computation       Context-Free-Language       ISRO-2017 December
Question 26 Explanation: 
L = {ap | p is a prime}
L can only be accepted by a Turing machine
Question 27
Consider the following statements about the context-free grammar
G = {S→ SS, S→ ab, S→ ba, S→ ^}
I. G is ambiguous
II. G produces all strings with an equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about?
A
I only
B
I and III only
C
II and III only
D
I, II and III
       Theory-of-Computation       Context-Free-Language       ISRO-2016
Question 27 Explanation: 
Is ambiguous, as it has two parse tree for the string “abbaba”

G doesn’t produce all strings of an equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:

Question 28

Which of the following sentences can be generated by

S -> aS | bA

A -> d | cA

A
bccdd
B
abbcca
C
abcabc
D
abcd
       Theory-of-Computation       Context-free-language       ISRO CS 2011
Question 28 Explanation: 
Given language:
S -> aS | bA
A -> d | cA
From the given productions, it is not possible to derive the sentence bccdd(two consecutive d’s).So option A is not correct.
In the string “abbcca”, there are two consecutive c’s followed by the letter ‘a’, This can’t be derived from the given productions,
From the given productions, it is also not possible to derive string which consists of the letter ‘c’ followed by ‘a’ , So the option (c ) also not correct
From given productions, we can generate the string “abcd”
Question 29

A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :

A
0
B
1
C
1 or more
D
2 or more
       Theory-of-Computation       Context-Free-Language       UGC-NET CS 2018 JUNE Paper-2
Question 29 Explanation: 
→ If we have two stacks then the stacks can act as a queue. Since a pushdown automata have a single stack as its memory device so if we have 1 more stack then the pushdown automata can be made to act as a turing machine.
→ So, total of 2 or more auxiliary memory are needed to make a pushdown automata behaves like a Turing machine.
Question 30

Pushdown automata can recognize language generated by

A
Only context free grammar
B
Only regular grammar
C
Context free grammar or regular grammar
D
Only context sensitive grammar
       Theory-of-Computation       Context-Free-Language       UGC-NET CS 2018 JUNE Paper-2
Question 30 Explanation: 
Let A ➝ aA | ∈ ; Here A is a regular grammar which can be accepted by the pushdown automata.
B ➝ aBb | ab ; Here B is a Context free grammar which can be accepted by the pushdown automata.
Question 31

Consider the following two Grammars :

    G1 : S → SbS|a
    G2 : S → aB|ab,  A → GAB|a, B → ABb|b

Which of the following option is correct ?

A
Only G1 is ambiguous
B
Only G2 is ambiguous
C
Both G1 and G2 are ambiguous
D
Both G1 and G2 are not ambiguous
       Theory-of-Computation       Context-Free-Language       UGC-NET CS 2018 JUNE Paper-2
Question 31 Explanation: 
A grammar is said to be ambiguous if we get two different parse trees using either Leftmost derivation only or Rightmost derivation only.
To generate string “ababa” using G1 grammar the two different parse tree possible are:
Question 32
Context free grammar can be recognized by
A
finite state automaton
B
2-way linear bounded automata
C
pushdown automata
D
Both (B) and (C)
       Theory-of-Computation       Context-Free-Language       Nielit Scientist-C 2016 march
Question 32 Explanation: 
Question 33

Consider the following language:

    L1 = { an+m bna| n,m ≥ 0}
    L2 = { an+m bn+m an+m |n,m ≥ 0}

Which one of the following is correct?

Code:
A
Only L1 is Context Free Language
B
Both L1 and L2 are not Context Free Language
C
Only L1 is Context Free Language
D
Both L1 and L2 are Context Free Language
       Theory-of-Computation       Context-Free-Language       UGC-NET CS 2018 DEC Paper-2
Question 33 Explanation: 
→ L1 is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L1 so we can say L1 is a CFL.
→ L2 is not a context free language because L is equivalent to language = {apbpap | p ≥ 0}.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L2.
L2 is not a CFL.
Question 34
If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
A
L1.L2
B
L1 ∩ L2
C
L1 ∩ R
D
L1 U L2
       Theory-of-Computation       Context-Free-Language       Nielit Scientist-B CS 2016 march
Question 34 Explanation: 
→ Intersection and complementation is not closed under context free languages(CFL).
→ L1 ∩ R is closed under CFL
→ L1.L2 and L1 U L2 is closed under CFL
Question 35
Which of the following are context free?
A = {anbnambm | m, n>=0}
B = {anbnambn | m, n>=0}
C = {ambn | m≠2n,m, n>=0}
A
A and B only
B
A and C only
C
B and C only
D
C only
       Theory-of-Computation       Context-Free-Language       ISRO DEC 2017 22- Soon
Question 35 Explanation: 
Statement-A: When 'a' will comes as input. We will push it on the top of stack and when 'b' will comes as input after 'a' we will pop one 'a' for each 'b'.
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
Statement-B: When last 'b' i.e., bn after am comes as input then top of the stack will contain am
So we can't compare an with anbn. Hence it is not CFL
Statement-C: It is a CFL
Question 36
Which of the following statements is/are TRUE ?
(i) The grammar S → SS | a is ambiguous (where S is the start symbol).
(ii) The grammar S → 0S1 | 01S | e is ambiguous (the special symbol e represents the empty string and S is the start symbol).
(iii) The grammar (where S is the start symbol).
S → T/U
T → x S y ? xy ? e
U → yT
generates a language consisting of the string yxxyy.
A
Only (i) and (ii) are TRUE
B
Only (i) and (iii) are TRUE
C
Only (ii) and (iii) are TRUE
D
All of (i), (ii) and (iii) are TRUE
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Nov- paper-2
Question 36 Explanation: 
Option (i) parse tree is ambiguous.

Option (ii): For producing string 01 it gives 2 parse tree. So, it is also ambiguous.
Option (iii): It is also true
Question 37
The context-free languages are closed for :
(i) Intersection
(ii) Union
(iii) Complementation
(iv) Kleene Star
then
A
(i) and (iv)
B
(i) and (iii)
C
(ii) and (iv)
D
(ii) and (iii)
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2004 Dec-Paper-2
Question 37 Explanation: 
The context free languages are closed under union and kleene star but it is not closed under intersection and complementation.
Note: Except intersection and complementation will closed under all operations in CFL.
Question 38
Identify the language which is not context-free.
A
L = { wwR ǀ wε{0,1}* }
B
L = { a​ n​ b​ n​ ǀ n≥0 }
C
L = { ww ǀ wε{0,1}* }
D
L = { a​ n​ b​ m​ c​ m​ d​ n​ ǀ n,m ≥0 }
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2005 june-paper-2
Question 38 Explanation: 
Option-A​ is a CFL because for this we can have a non deterministic pushdown automata which will accept the string by exploring all the possibilities on each input character.
Option-B​ is correct because we can have a deterministic pushdown automata which will push all the "a" as they come as input and when "b" comes as input for every "b" one "a" will be popped. So in this way we can design a pushdown automata which will accept a​ n​ b​ n​ . Hence a​ n​ b​ n​ is a CFL.
Option-C​ is not a CFL because we can't design a pushdown which can accept CFL. Suppose a string "abcabc". Now let's say pushdown automata recognize w=abc after symbol "c" now when "a" come as input after "c" the pushdown automata have to pop "a" i.e. initial input symbol "a" but top of the stack contains "c" as top element. So in this way we can't have any pushdown automata which can accept "ww" language. So it is not a CFL.
Option-D​ is a CFL because we can design a pushdown automata for a​ n​ b​ m​ c​ m​ d​ n​ . The push down automata will push "a" and "b" as the come as input symbol. When "c" came as input then for each "c" one "b" is popped from top of the stack. And when "d" will come as input symbol the top of stack will contain only a's so for every "d" one "a" is popped . In this way we can design a pushdown automata for a​ n​ b​ m​ c​ m​ d​ n​ .
So, option-C is correct answer.
Question 39
The following Context-Free Grammar (CFG) :
S → aB | bA
A → a | as | bAA
B → b | bs | aBB
will generate
A
odd numbers of a’s and odd numbers of b’s
B
even numbers of a’s and even numbers of b’s
C
equal numbers of a’s and b’s
D
different numbers of a’s and b’s
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2014 Dec-Paper-2
Question 39 Explanation: 
Option A is false: as it generate string "abab" which has even number of a's and b's.
Option B is false: as it generate string "ab" which has odd number of a's and b's.
Option D is false: as it always generate one "a" along with one "b". So it will always generate equal number of a's and b's and will never generate different number of a's and b's.
Hence option C is correct.
Question 40
Consider the following language:
L​ 1​ = { a n+m b n a m | n, m ≥ 0 }
L​ 2​ = { a n+m b n+m a n+m |n, m ≥ 0 }
Which one of the following is correct?
A
Only L​ 1​ is Context Free Language
B
Both L​ 1​ and L​ 2​ are not Context Free Language
C
Only L​ 1​ is Context Free Language
D
Both L​ 1​ and L​ 2​ are Context Free Language
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2018-DEC Paper-2
Question 40 Explanation: 
→ L​ 1​ is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L​ 1​ so we can say L​ 1​ is a CFL.
→ L​ 2​ is not a context free language because L is equivalent to language= {a​ p​ b​ p​ a​ p​ | p ≥ 0 }.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L​ 2​ .
L​ 2​ is not a CFL.
Question 41
Which one of the following statement is false ?
A
Context-free languages are closed under union.
B
Context-free languages are closed under concatenation.
C
Context-free languages are closed under intersection.
D
Context-free languages are closed under Kleene closure
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2011 Dec-Paper-2
Question 41 Explanation: 
Context-free languages are closed under Union,Concatenation and Kleene closure.
Context-free languages are not closed under set difference,Complementation and intersection.
Question 42
Any string of terminals that can be generated by the following CFG
S ⟶ XY
X ⟶ aX | bX | a
Y ⟶ Ya | Yb |a
A
has at least one b
B
should end in an ‘a’
C
has no consecutive a’s or b’s
D
has at least two a’s
       Theory-of-Computation       Context-Free-Language       NIELIT Junior Teachnical Assistant_2016_march
Question 43
Consider the following languages: L1 = {am bn │ m ≠ n} L2 = {am bn │ m = 2n+1} L3 = {am bm │ m ≠ 2n} Which one of the following statement is correct ?
A
Only L1 and L2 are context free languages
B
Only L1 and L3 are context free languages
C
Only L2 and L3 are context free languages
D
L1, L2 and L3 are context free languages
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Nov- paper-3
Question 43 Explanation: 
L1={am bn | m≠n }
→ It means m could be greater than or less than ‘n’ but m will not be equal to ‘n’.
→ Since for accepting the language L1 we need a storage so then no. of a’s can be stored in it and when b’s come as input a’s and b’s can be compared.
→ Since finite automata do not have a storage element hence the language is not regular.
→ Now state transition diagram to check whether L1 is CFL or not:

→ Hence L2 is also a CFL.
L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Question 44
Given the following two languages : L1 = {an bn | n ≥ 0, n ≠ 100} L2 = {w ∈ {a, b, c}*| na(w) = nb(w) = nc(w)} Which of the following options is correct ?
A
Both L1 and L2 are not context free language
B
Both L1 and L2 are context free language.
C
L1 is context free language, L2 is not context free language.
D
L1 is not context free language, L2 is context free language.
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Jan- paper-3
Question 44 Explanation: 
Statement 1: L1 is a context free language because we can easily construct a pushdown automata which can push all a's onto the top of stack and then when b's comes as input for each "b" one "a" will be popped up. If number of a's is equal to number of b's then final stage is reached and string is accepted except the case when 100th "b" came as input we can go to a non final state and if after that any "b" came as input then the transaction can take place to a final state according to the equal number of b's and a's else we remain on that non-final state. So in this way a pushdown automata can be constructed for given language.
Hence L1 is a context free language.
Statement 2: L2 is not a context free language because we can push a's on the top of stack and when b's came as input we can pop one "a" for each "b" so in this way stack will get empty before comparing equal number of a, b and c. For comparing number of "c" the will be no "a or b" on the top of stack.
Hence L2 is not a context free language.
Question 45
Given the following two statements :
A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} ∪ {an b2n} is linear, but not deterministic context free language.
Which of the following options is correct ?
A
Both (A) and (B) are false.
B
Both (A) and (B) are true.
C
(A) is true, (B) is false.
D
(A) is false, (B) is true.
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2017 Jan- paper-3
Question 45 Explanation: 
Statement-1:
A linear grammar is a context free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.
ex-1: S→ aSb | ab
ex-2: S→ aS | Sb | ϵ
The grammar for (a)--> S→ϵ,S→SaSbS,S→SbSaS }

which is not linear. It is DCFL
Statement-2:
The example grammar is
S→ aSb | aSbb | ϵ
Hence it is linear language and it is not DCFL.
Question 46
Let L = {0n1n|n ≥ 0} be a context free language. Which of the following is correct ?
A
L’ is context free and Lk is not context free for any k ≥ 1.
B
L’ is not context free and Lk is not context free for any k ≥ 1.
C
Both L’ and Lk is for any k ≥ 1 are context free.
D
Both L’ and Lk is for any k ≥ 1 are not context free.
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2016 July- paper-3
Question 47
Given the following two languages: L1 = {an b an |n > 0} L2 = {an b an bn + 1|n > 0} Which of the following is correct ?
A
L1 is context free language and L2 is not context free language
B
L1 is not context free language and L2 is context free language
C
Both L1 and L2 are context free languages
D
Both L1 and L2 are not context free languages
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2015 Dec - paper-3
Question 47 Explanation: 
L1 is CFL because we can push all a's first on the top of stack when a "b" come as input change the state and don't push "b" on stack now when "a" comes after "b" then for each "a" pop one "a" from top of stack.
L2 is not CFL because we can push all a's first on the top of stack when a "b" come as input change the state and don't push "b" on stack now when "a" comes after "b" then for each "a" pop one "a" from top of stack. . Bur for "b" that comes in last we don't have "a" to compare them. So it is not CFL language.
Question 48
Consider the following languages: L1 = {anbncm} ∪ {an bm cm}, n. m ≥ o L2 = {ωωR |ω ∈ {a, b}*} Where R represents reversible operation. Which one of the following is (are) inherently ambiguous language(s)?
A
only L1
B
only L2
C
both L1 and L2
D
neither L1 nor L2
       Theory-of-Computation       Context-Free-Language       UGC-NET DEC-2019 Part-2
Question 48 Explanation: 
A language is inherently ambiguous:
If for a language every existing grammar is ambiguous then that language is called inherently ambiguous language. By this definition of inherently ambiguous, we can conclude that for an inherently ambiguous language an equivalent unambiguous grammar can't be found.
There are several languages (special types ) which are inherently ambiguous.
For example : L= {ai bj ck | i=j or c=k} is inherently ambiguous
The reason is : It is union of two languages {an bn cm} U {an bm cm}
So it will have grammar
S-> A | B
A-> PQ
P->aPb | ab
Q-> cQ | c
B-> UV
U-> aU | a
V-> bVc | bc
Grammar A generates equal number of a's and b's and any number of c's
Grammar B generates equal number of b's and c's and any number of a's
So the strings which have equal numbers of a's, b's and c's can be generated by A or B
So for these strings we always have two parse trees.
Hence this language is ambiguous as we cannot make an unambiguous grammar for it.
Question 49

Consider the following statements with respect to the language L = {anbn | n ≥ 0}



Which one of the following is correct?
A
only S1 and S2
B
only S1 and S3
C
only S2 and S3
D
S1, S2 and S3
       Theory-of-Computation       Context-Free-Language       UGC-NET DEC-2019 Part-2
Question 49 Explanation: 
S1 is correct because L2 means L.L i.e resulting language will be L2 = {anbnanbn | n ≥ 0} which is a context free language.
Since context free languages are closed under kleen closure so Lk is context-free language for any given k ≥ 1. Hence S2 is correct.
Complement of given language L will be a language accepting all strings other than {anbn | n ≥ 0}. And we can easily design a pushdown automata which rejects {anbn | n ≥ 0} and accepts all string other than this. And as we know, context free languages are closed under kleen closure. Hence S3 is correct.
Question 50
Consider the following languages over the alphabet {a, b, c, d}

Which of these languages is/are context-free?
A
None of them.
B
C
D
All of them.
       Theory-of-Computation       Context-Free-Language       CMI PHD 2022
Question 50 Explanation: 
Question 51
Context free languages are closed under
A
Union , intersection
B
Union , kleene closure
C
Intersection, complement
D
Complement, kleene closure
       Theory-of-Computation       Context-Free-Language       ISRO CS 2020       Video-Explanation
Question 51 Explanation: 
CFL are closed under Union and Kleene closure but not closed under complement, intersection.
Question 52

Which of the following is/are correct
I. A language is context free if and only if it accepted by PDA
II. PDA is a finite automata with push down stack

A
Only II is true
B
Both I and II are false
C
Both I and II are true
D
Only I is true
       Theory-of-Computation       Context-Free-Language       CIL 2020
Question 52 Explanation: 
S1 is true, because if a language is not accepted by PDA that means it is not context free. So we can say that a language is context free if and only if it is accepted by PDA.
S2 is true, Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages. A Pushdown Automata (PDA) can be defined as : ... In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.
Question 53
The language L = {anbmcndm |n≥1, m≥1}
A
Is context free
B
Is not context free
C
Abstract problem of checking number of formal and actual parameters
D
Both (B) and (C).
       Theory-of-Computation       Context-Free-Language       TNPSC-2012-Polytechnic-CS
Question 53 Explanation: 
The given language is not context free because first we will push a’s and then we cant push b’s because we have to pop the a’s from the stack with corresponding c’s. And since we cant push b’s which cannot be compared by further d’s which is dependent on b’s.
Also given language is abstract problem of checking number of formal and actual parameters.
Question 54

According to pumping lemma for context free languages :

Let L be an infinite context free language, then there exists some positive integer m such

that any w ∈ L with | w | ≥ m can be decomposed as w = u v x y z
A
with | vxy | ≤ m such that uvi xyi z ∈ L for all i = 0, 1, 2
B
with | vxy | ≤ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
C
with | vxy | ≥ m, and | vy | ≤ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
D
with | vxy | ≥ m, and | vy | ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….
       Theory-of-Computation       Context-Free-Language       UGC NET CS 2014 Dec - paper-3
Question 54 Explanation: 
Let L be an infinite context free language, then there exists some positive integer m such that any w ∈ L with | w | ≥ m can be decomposed as w = u v x y z with | vxy | ≤ m, and | vy | ≥ 1, such that uvi xy i z ∈ L for all i = 0, 1, 2, …….
Question 55
Let L1={anbm | m,n >=0 and m>=n} and L2={anbm | m,n >=0 and m he language L1 U L2 is:
A
Regular, but not context free
B
Context free, but not regular
C
Both regular and context free
D
Neither regular nor context free
       Theory-of-Computation       Context-Free-Language       CMI 2019
Question 55 Explanation: 
Question 56
Which of the following statements is true?
A
The union of two context free languages is context free.
B
The intersection of two context free languages is context free.
C
The complement of a context free language is context free.
D
If a language is context free, it can always be accepted by a deterministic pushdown automaton.
       Theory-of-Computation       Context-Free-Language       UGC NET JRF November 2020 Paper-2
Question 56 Explanation: 

Option 4 is incorrect because CFL includes both DCFL and NDCFL and NDCFL are accepted by only non-deterministic pushdown automata, they can’t be accepted by Deterministic PDA.
There are 56 questions to complete.