ContextFreeLanguage
Question 1 
Which one of the following languages over Σ = {a,b} is NOT contextfree?
{ww^{R} w ∈ {a,b}*}  
{wa^{n}w^{R}b^{n} w ∈ {a,b}*, n ≥ 0}  
{a^{n}b^{i}  i ∈ {n, 3n, 5n}, n ≥ 0}  
{wa^{n}b^{n}w^{R} w ∈ {a,b}*, n ≥ 0} 
This is similar to language
L = {a^{n}b^{m}c^{n}d^{m}  n, m > 0}
Suppose we push “w” then a^{n} and then w^{R}, now we cannot match b^{n} with a^{n}, because in top of stack we have w^{R}.
Question 2 
I. {a^{m} b^{n} c^{p} d^{q} ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {a^{m} b^{n} c^{p} d^{q} ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {a^{m} b^{n} c^{p} d^{q} ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {a^{m} b^{n} c^{p} d^{q} ∣ mn = p + q, where m, n, p, q ≥ 0}
Which of the above languages are contextfree?
I and IV only  
I and II only  
II and III only  
II and IV only 
mn = qp
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) a^{m} b^{n} c^{p} d^{q}  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) a^{m} b^{n} c^{p} d^{q}  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 
G_{1}: S → aSbT, T → cTϵ
G_{2}: S → bSaT, T → cTϵ
The language L(G_{1}) ∩ L(G_{2}) is
Finite  
Not finite but regular  
ContextFree but not regular  
Recursive but not contextfree 
{ϵ, c, cc, ccc, … ab, aabb, aaabbb….acb, accb… aacbb, aaccbb, …}
Strings generated by G_{2}:
{ϵ, c, cc, ccc, … ba, bbaa, bbbaaa….bca, bcca… bbcaa, bbccaa, …}
The strings common in L (G_{1}) and L (G_{2}) are:
{ϵ, c, cc, ccc…}
So, L (G_{1}) ∩ L (G_{2}) can be represented by regular expression: c*
Hence the language L (G_{1}) ∩ L (G_{2}) is “Not finite but regular”.
Question 4 
Let L_{1} = {a^{n} b^{n} c^{m}│m,n ≥ 0} and L_{2} = {a^{m} b^{n} c^{n}│m,n ≥ 0}
Which of the following are contextfree languages?
I. L_{1} ∪ L_{2}
II. L_{1} ∩ L_{2}
I only  
II only  
I and II  
Neither I nor II 
Strings in L_{2} = {ϵ, a, aa, …., bc, bbcc,…., abc, aabc,…, abbcc, aabbcc, aaabbcc,..}
Strings in L_{1} ∪ L_{2} ={ϵ, a, aa, .., c, cc,.. ab, bc, …, aabb, bbcc,.., abc, abcc, aabc,…}
Hence (L_{1} ∪ L_{2}) will have either (number of a’s = equal to number of b’s) OR (number of b’s = number of c’s).
Hence (L_{1} ∪ L_{2}) is CFL.
Strings in L_{1} ∩ L_{2} = {ϵ, abc, aabbcc, aaabbbccc,…}
Hence (L_{1} ∩ L_{2}) will have (number of a’s = number of b’s = number of c’s)
i.e., (L_{1} ∩ L_{2}) = {a^{n}b^{n}c^{n}  n ≥ 0} which is CSL.
Question 5 
Let L_{1}, L_{2} be any two contextfree languages and R be any regular language. Then which of the following is/are CORRECT?
I, II and IV only  
I and III only  
II and IV only  
I only 
CFL is not closed under complementation.
So L_{1} compliment may or may not be CFL. Hence is Context free, is a false statement.
L_{1} – R means and Regular language is closed under compliment, so
is also a regular language, so we have now L_{1} ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L_{1}∩R is context free.
CFL is not closed under INTERSECTION, so L_{1} ∩ L_{2} may or may not be CFL and hence IV^{th} is false.
Question 6 
L_{1}= {a^{p}│p is a prime number}
L_{2}= {a^{n}b^{mc2m n ≥ 0, m ≥ 0} L3= {anbnc2n│ n ≥ 0} L4= {anbn│ n ≥ 1} Which of the following are CORRECT? I. L1 is contextfree but not regular. II. L2 is not contextfree. III. L3 is not contextfree but recursive. IV. L4 is deterministic contextfree.}
I, II and IV only  
II and III only  
I and IV only  
III and IV only 
L_{2} = {a^{n} b^{m} c^{2m}│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 L^{2} is Context free and II is true.
L_{3} = {a^{n} b^{n} c^{2n}│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
L_{4} = {a^{n} b^{n}│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 
L_{1} = {a^{n} b^{m} c^{n+m}: m,n ≥ 1}
L_{2}= {a^{n} b^{n} c^{2n}: n ≥ 1}
Which one of the following is TRUE?
Both L_{1} and L_{2} are contextfree.  
L_{1} is contextfree while L_{2} is not contextfree.  
L_{2} is contextfree while L_{1} is not contextfree.  
Neither L_{1} nor L_{2} is contextfree. 
At the end if input and stack is empty then accept.
Hence, it is CFL.
But L_{2} can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1^{st} comparison:
number of a’s = number of b’s
2^{nd} 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 contextfree?
 L1 = {a^{m}b^{n}a^{n}b^{m} ⎪ m, n ≥ 1}
L2 = {a^{m}b^{n}a^{m}b^{n} ⎪ m, n ≥ 1}
L3 = {a^{m}b^{n} ⎪ m = 2n + 1}
L_{1} and L_{2} only  
L_{1} and L_{3} only  
L_{2} and L_{3} only  
L_{3} only 
L_{2}: 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.
L_{3}: 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 = {0^{i}1^{j}  i != j}.
L2 = {0^{i}1^{j}  i = j}.
L3 = {0^{i}1^{j}  i = 2j+1}.
L4 = {0^{i}1^{j}  i != 2j}.
Which one of the following statements is true?
Only L2 is context free  
Only L2 and L3 are context free  
Only L1 and L2 are context free  
All are context free 
Question 10 
The language generated by the above grammar over the alphabet {a,b} is the set of
all palindromes.  
all odd length palindromes.  
strings that begin and end with the same symbol.  
all even length palindromes. 
Question 11 
Let L_{1} = {0^{n+m}1^{n}0^{m}n,m ≥ 0}, L_{2} = {0^{n+m}1^{n+m}0^{m}n,m ≥ 0}, and L_{3} = {0^{n+m}1^{n+m}0^{n+m}n,m ≥ 0}. Which of these languages are NOT context free?
L_{1} only  
L_{3} only  
L_{1} and L_{2}  
L_{2} and L_{3} 
But for L_{2} and L_{3} PDA implementation is not possible. The reason is, in L_{2} 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 L_{3} also has the similar reason.
Question 12 
Consider the languages:
L_{1} = {a^{n}b^{n}c^{m} n,m > 0} and L_{2} = {a^{n}b^{m}c^{m} n,m > 0}
Which one of the following statements is FALSE?
L_{1} ∩ L_{2} is a contextfree language  
L_{1} ∪ L_{2} is a contextfree language  
L_{1} and L_{2} are contextfree languages  
L_{1} ∩ L_{2} is a context sensitive language 
CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
Question 13 
Consider the languages:
L_{1} = {ww^{R} w ∈ {0,1}*} L_{2} = {w#w^{R}  w ∈ {0,1}*}, where # is a special symbol L_{3} = {ww  w ∈ (0, 1)*}
Which one of the following is TRUE?
L_{1} is a deterministic CFL
 
L_{2} is a deterministic CFL  
L_{3} is a CFL, but not a deterministic CFL  
L_{3} is a deterministic CFL 
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
Question 14 
Contextfree languages are closed under:
Union, intersection  
Union, Kleene closure  
Intersection, complement  
Complement, Kleene closure 
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.
Theory Explanation. 
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
the set of all binary strings with unequal number of 0’s and 1’s  
the set of all binary strings including the null string  
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  
None of the above 
Question 17 
The grammar whose productions are
→ if id then → if id then else → id := id
is ambiguous because
the sentence if a then if b then c:=d  
the left most and right most derivations of the sentence if a then if b then c:=d give rise top different parse trees  
the sentence if a then if b then c:=d else c:=f has more than two parse trees  
the sentence if a then if then c:=d else c:=f has two parse trees 
"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.
True  
False 
Question 19 
L={w x w^{R} x^{R }  w, x ∈ {0,1}* }  
L={w w^{R} x x^{R}  w, x ∈ {0,1}* }  
L={w x x^{R} w^{R}  w, x ∈ {0,1}* }  
L={w x w^{R}  w, x ∈ {0,1}* } 
Option A: L={w x w^{R} x^{R}  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 w^{R} x x^{R}  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 x^{R} w^{R}  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 w^{R}  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 
Question 21 
L 1 and L 2 are regular.  
L 1 and L 2 are contextfree.  
L 1 is regular and L 2 is contextfree.  
L 1 and L 2 are contextfree but not 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 
L 1 is not contextfree but L 2 and L 3 are deterministic contextfree.  
Neither L 1 nor L 2 is contextfree.  
Neither L 1 nor its complement is contextfree. 
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 (nonCFL).
So A is a true statement and rest all are false statements.
Question 23 
2x – 1  
2x  
2x + 1  
2^{x} 
→ For CNF, it is 2x  1
→ For GNF, it is x
Question 24 
S → ABCc ∣ bc
BA → AB
Bb → bb
Ab → ab
Aa → aa
Which of the following sentences can be derived by this grammar?
abc  
aab  
abcc  
abbc 
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 
not contextfree, not linear  
not contextfree, linear  
contextfree, not linear  
contextfree, linear 
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of nonterminals
It is clearly seen that given grammar is not linear but contextfree.
Question 26 
Then which of the following is true?
It is not accepted by a Turing Machine  
It is regular but not contextfree  
It is contextfree but not regular  
It is neither regular nor contextfree but accepted by a Turing Machine 
L can only be accepted by a Turing machine
Question 27 
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?
I only  
I and III only  
II and III only  
I, II and III 
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
bccdd  
abbcca  
abcabc  
abcd 
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 :
0  
1  
1 or more  
2 or more

→ 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
Only context free grammar  
Only regular grammar  
Context free grammar or regular grammar  
Only context sensitive grammar

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 → SbSa
G2 : S → aBab, A → GABa, B → ABbb
Which of the following option is correct ?
Only G1 is ambiguous  
Only G2 is ambiguous  
Both G1 and G2 are ambiguous  
Both G1 and G2 are not ambiguous

To generate string “ababa” using G1 grammar the two different parse tree possible are:
Question 32 
finite state automaton  
2way linear bounded automata  
pushdown automata  
Both (B) and (C) 
Question 33 
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?
Code:Only L_{1} is Context Free Language
 
Both L_{1} and L_{2} are not Context Free Language
 
Only L_{1} is Context Free Language  
Both L_{1} and L_{2} are Context Free Language

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 34 
L1.L2  
L1 ∩ L2  
L1 ∩ R  
L1 U L2 
→ L1 ∩ R is closed under CFL
→ L1.L2 and L1 U L2 is closed under CFL
Question 35 
A = {a^{n}b^{n}a^{m}b^{m } m, n>=0}
B = {a^{n}b^{n}a^{m}b^{n}  m, n>=0}
C = {a^{m}b^{n}  m≠2n,m, n>=0}
A and B only  
A and C only  
B and C only  
C only 
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
StatementB: When last 'b' i.e., b^{n} after a^{m} comes as input then top of the stack will contain a^{m}
So we can't compare a^{n} with a^{n}b^{n}. Hence it is not CFL
StatementC: It is a CFL
Question 36 
(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.
Only (i) and (ii) are TRUE  
Only (i) and (iii) are TRUE
 
Only (ii) and (iii) are TRUE  
All of (i), (ii) and (iii) are TRUE 
Option (ii): For producing string 01 it gives 2 parse tree. So, it is also ambiguous.
Option (iii): It is also true
Question 37 
(i) Intersection
(ii) Union
(iii) Complementation
(iv) Kleene Star
then
(i) and (iv)  
(i) and (iii)  
(ii) and (iv)  
(ii) and (iii) 
Note: Except intersection and complementation will closed under all operations in CFL.
Question 38 
L = { wwR ǀ wε{0,1}* }  
L = { a ^{n} b^{ n} ǀ n≥0 }  
L = { ww ǀ wε{0,1}* }  
L = { a ^{n} b^{ m} c^{ m} d^{ n} ǀ n,m ≥0 } 
OptionB 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.
OptionC 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.
OptionD 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, optionC is correct answer.
Question 39 
S → aB  bA
A → a  as  bAA
B → b  bs  aBB
will generate
odd numbers of a’s and odd numbers of b’s  
even numbers of a’s and even numbers of b’s  
equal numbers of a’s and b’s  
different numbers 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 
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?
Only L_{ 1} is Context Free Language  
Both L _{1} and L_{ 2} are not Context Free Language  
Only L _{1} is Context Free Language  
Both L_{ 1} and L_{ 2} are Context Free Language 
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 
Contextfree languages are closed under union.  
Contextfree languages are closed under concatenation.  
Contextfree languages are closed under intersection.  
Contextfree languages are closed under Kleene closure 
Contextfree languages are not closed under set difference,Complementation and intersection.
Question 42 
S ⟶ XY
X ⟶ aX  bX  a
Y ⟶ Ya  Yb a
has at least one b  
should end in an ‘a’  
has no consecutive a’s or b’s  
has at least two a’s 
Question 43 
Only L_{1} and L_{2} are context free languages  
Only L_{1} and L_{3} are context free languages  
Only L_{2} and L_{3} are context free languages  
L_{1}, L_{2} and L_{3} are context free languages 
→ 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 L_{2} 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 
Both L_{1} and L_{2} are not context free language  
Both L_{1} and L_{2} are context free language.  
L_{1} is context free language, L_{2} is not context free language.  
L_{1} is not context free language, L_{2} is context free 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 
A. L = {wn_{a}(w) = n_{b}(w)} is deterministic context free language, but not linear.
B. L = {a^{n} b^{n}} ∪ {a^{n} b^{2n}} is linear, but not deterministic context free language.
Which of the following options is correct ?
Both (A) and (B) are false.  
Both (A) and (B) are true.  
(A) is true, (B) is false.  
(A) is false, (B) is true. 
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.
ex1: S→ aSb  ab
ex2: S→ aS  Sb  ϵ
The grammar for (a)> S→ϵ,S→SaSbS,S→SbSaS }
which is not linear. It is DCFL
Statement2:
The example grammar is
S→ aSb  aSbb  ϵ
Hence it is linear language and it is not DCFL.
Question 46 
L’ is context free and L^{k} is not context free for any k ≥ 1.  
L’ is not context free and L^{k} is not context free for any k ≥ 1.  
Both L’ and L^{k} is for any k ≥ 1 are context free.  
Both L’ and L^{k} is for any k ≥ 1 are not context free. 
Question 47 
L_{1 }is context free language and L_{2 }is not context free language  
L_{1 }is not context free language and L_{2 }is context free language
 
Both L_{1} and L_{2 }are context free languages  
Both L_{1} and L_{2 }are not context free languages 
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 
only L_{1}  
only L_{2}  
both L_{1} and L_{2}  
neither L_{1} nor L_{2} 
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= {a^{i} b^{j} c^{k}  i=j or c=k} is inherently ambiguous
The reason is : It is union of two languages {a^{n} b^{n} c^{m}} U {a^{n} b^{m} c^{m}}
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 = {a^{n}b^{n}  n ≥ 0}
Which one of the following is correct?
only S_{1} and S_{2}  
only S_{1} and S_{3}  
only S_{2} and S_{3}  
S_{1}, S_{2} and S_{3} 
Since context free languages are closed under kleen closure so L^{k} is contextfree language for any given k ≥ 1. Hence S2 is correct.
Complement of given language L will be a language accepting all strings other than {a^{n}b^{n}  n ≥ 0}. And we can easily design a pushdown automata which rejects {a^{n}b^{n}  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 
Which of these languages is/are contextfree?
None of them.  
All of them. 
Question 51 
Union , intersection  
Union , kleene closure  
Intersection, complement  
Complement, kleene closure 
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
Only II is true  
Both I and II are false
 
Both I and II are true
 
Only I is true

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 
Is context free  
Is not context free  
Abstract problem of checking number of formal and actual parameters  
Both (B) and (C).

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
with  vxy  ≤ m such that uvi xyi z ∈ L for all i = 0, 1, 2  
with  vxy  ≤ m, and  vy  ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….  
with  vxy  ≥ m, and  vy  ≤ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, …….  
with  vxy  ≥ m, and  vy  ≥ 1, such that uvi xyi z ∈ L for all i = 0, 1, 2, ……. 
Question 55 
Regular, but not context free  
Context free, but not regular  
Both regular and context free  
Neither regular nor context free 
Question 56 
The union of two context free languages is context free.  
The intersection of two context free languages is context free.  
The complement of a context free language is context free.  
If a language is context free, it can always be accepted by a deterministic pushdown automaton. 
Option 4 is incorrect because CFL includes both DCFL and NDCFL and NDCFL are accepted by only nondeterministic pushdown automata, they can’t be accepted by Deterministic PDA.