LanguagesandGrammars
Question 1 
A language with string manipulation facilities uses the following operations.
concat(sl, s2) concatenates string s1 with s2.
The output of concat(head(s), head(tail(tail(s)))), where s is acbc is
ab  
ba  
ac  
as 
Question 1 Explanation:
Question 2 
Given the following statements:
S1 : Every contextsensitive language L is recursive
S2 : There exists a recursive language that is not contextsensitive
Which statements are true?
S1 : Every contextsensitive language L is recursive
S2 : There exists a recursive language that is not contextsensitive
Which statements are true?
Only S1 is correct  
Only S2 is correct  
Both S1 and S2 are not correct  
Both S1 and S2 are correct 
Question 2 Explanation:
According to the Chomsky hierarchy, both the statements are correct.
Question 3 
Identify the language generated by the following grammar
S > AB
A > aAbϵ
B > bB b
S > AB
A > aAbϵ
B > bB b
{a^{m}b^{n}  n>=m, m>0}  
{a^{m}b^{n}  n>=m, m>=0}  
{a^{m}b^{n}  n>m, m>0}  
{a^{m}b^{n}  n>m, m>=0} 
Question 3 Explanation:
The language generated by given grammar is  L={b,bb,abb,abbb,ababb}
Hence it is a^{m}b^{n}  n>m, m>=0
Hence it is a^{m}b^{n}  n>m, m>=0
Question 4 
S → aSa ∣ bSb ∣ a ∣ b
The language generated by the above grammar over the alphabet is the set of
all palindromes  
all odd length palindromes  
strings that begin and end with the same symbol  
all even length palindromes 
Question 4 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 5 
What is the highest type number that can be assigned to the following grammar?
S → Aa
A → Ba
B → abc
S → Aa
A → Ba
B → abc
Type 0  
Type 1  
Type 2  
Type 3 
Question 5 Explanation:
Grammar is belongs to Type 0 ,Type 1,Type 2,Type 3 because it is regular. Option D is right answer because they are asking only highest type number.
Question 6 
What is the number of steps required to derive the string ((() ()) ()) for the following grammar?
S → SS
S → (S)
S → ε
S → SS
S → (S)
S → ε
10  
15  
12  
16 
Question 6 Explanation:
The required string consists of only only matched parenthesis enclosed with parentheses.
To generate the string ((() ()) ()) , we need to perform the steps sequentially.
As the string starts with left parentheses, we will start with the production S → (S).
Depending upon the string we will go for either left or right tree generation.
1) S → (S) // Replacing S by (S)
2) S → (SS) // Replacing by S by SS
3) S → ((S)S) //Replacing S by(S)
4) S → ((SS)S)// Replacing S by SS
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S)) [S → ε]
8) S → ((()(S))S) [S → ε]
9) S → ((()())S) [S → ε]
10) S → ((()()))
To generate the string ((() ()) ()) , we need to perform the steps sequentially.
As the string starts with left parentheses, we will start with the production S → (S).
Depending upon the string we will go for either left or right tree generation.
1) S → (S) // Replacing S by (S)
2) S → (SS) // Replacing by S by SS
3) S → ((S)S) //Replacing S by(S)
4) S → ((SS)S)// Replacing S by SS
5) S → (((S)S))S)
6) S → (((S)(S))S)
7) S → (((S)(S))(S)) [S → ε]
8) S → ((()(S))S) [S → ε]
9) S → ((()())S) [S → ε]
10) S → ((()()))
Question 7 
Consider the following grammar.
S → AB
A → a
A → BaB
B → bbA
Which of the following statements is FALSE?
S → AB
A → a
A → BaB
B → bbA
Which of the following statements is FALSE?
The length of every string produced by this grammar is even  
No string produced by this grammar has three consecutive a’s  
The length of substring produced by B is always odd  
No string produced by this grammar has four consecutive b’s 
Question 7 Explanation:
Question 8 
The number of substrings that can be formed from string given by “a d e f b g h n m p” is
10  
45  
56  
55 
Question 8 Explanation:
If we have no repetition in a string then the number of substrings can be found using the formula :
n*(n+1)/2 + 1
We have added 1 because it may include a NULL string also.
The number of substrings = 10*(11)/2 +1
The number of substrings = 56
n*(n+1)/2 + 1
We have added 1 because it may include a NULL string also.
The number of substrings = 10*(11)/2 +1
The number of substrings = 56
Question 9 
Which of the following correctly defines kleene closure?
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string)
 
It is the finite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string)
 
It is the finite set of all possible strings of all possible lengths over Σ(input set)
 
It is the infinite set of all possible strings of all possible lengths over Σ(input set) 
Question 9 Explanation:
Kleene closure
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
Question 10 
A language is a subset of Σ* for some alphabet Σ. If a language takes all possible strings of length 2 over Σ = {a,b}, then, which of the below is correct?
L = {ab,bb,ba}
 
L = {aa,ab,ba,bb}
 
L = {ab,bb,aa}
 
L = {ab,ba,aa} 
Question 10 Explanation:
→ All possible strings of length 2 over Σ = {a,b} = 4(aa,ab,ba,bb}.
→ We are computing all possible strings using 2^{n} formula. Where n is number of strings.
→ We are computing all possible strings using 2^{n} formula. Where n is number of strings.
Question 11 
Which of the definitions generates the same languages as L, where
L={ x^{n} y^{n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x ^{+} y ^{+}
L={ x^{n} y^{n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x ^{+} y ^{+}
i only  
i and ii only  
ii and iii only  
ii only 
Question 11 Explanation:
The language L={ x ^{n} y^{ n} , n>=1 }
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1:E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X ^{+} means one or more x’s
Y ^{+} means one or more y’s
Definition 2 :
The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x^{ +} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1:E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X ^{+} means one or more x’s
Y ^{+} means one or more y’s
Definition 2 :
The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x^{ +} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Question 12 
Which of the definitions generates the same languages as L, where
L={ x^{ n} y^{ n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x^{ +} y^{ +}
L={ x^{ n} y^{ n} , n>=1 }
i. E→ xEy xy
ii.xyx ^{+} x yy^{ +}
iii. x^{ +} y^{ +}
i only  
i and ii only  
ii and iii only  
ii only 
Question 12 Explanation:
The language L={ x ^{n} y^{ n} , n>=1 }
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1 :E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X
+
means one or more x’s
Y
+
means one or more y’s
Definition 2 : The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x ^{+} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
For n=1, xy
n=2,x ^{2} y^{ 2}
n=3,x ^{3} y^{ 3}
In the above language , there are equal number of x’s followed by y’s
Definition1 :E→ xEy xy → xEy → xxEyy → xxxEyyy → xxxxyyyy
Which is nothing but equal number of x’s followed by equal number of y’s
X
+
means one or more x’s
Y
+
means one or more y’s
Definition 2 : The expression xyx ^{+} x yy^{ +} gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition2 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Definition 3 :
The expression x ^{+} y^{ +} gives xy, xxy,xxxy,xyy,xyyy and so on strings.
The definition3 won’t give equal number of x’s followed by y’s
It generates any number of x’s followed by any number of y’s.
Question 13 
For the context free grammar G:
R → XRXS, S → aTbTa, T → XTXXϵ X → ab
The strings which are not in L(G) are:
ab,ba,aab
 
abb,aabab
 
a,b,aa
 
a,b,ϵ

Question 13 Explanation:
We can’t generate the strings “a” and “b” because the Starting symbol is R→ XRXS.
Question 14 
Which of the following is FALSE?
The grammar S→aSaSbS∈, where S is the only nonterminal symbol, and ∈ is the null string, is ambiguous.  
An unambiguous grammar has same leftmost and rightmost derivation.  
An ambiguous grammar can never be LR(k) for any k.  
Recursive descent parser is a topdown parser. 
Question 14 Explanation:
OptionA: TRUE: S is non terminal symbol, ∈ is the null string, is ambiguous.
OptionB: FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
OptionC: TRUE: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
OptionD: TRUE: Recursive descent parser is a topdown parser
OptionB: FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
OptionC: TRUE: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
OptionD: TRUE: Recursive descent parser is a topdown parser
Question 15 
Which sentence can be generated by
S→d/bA
A→d/ccA
S→d/bA
A→d/ccA
bccddd  
aabccd  
ababccd  
abbbd  
None of the above 
Question 15 Explanation:
Here, there is no terminal symbol ‘a’, so the answer never be option B,C,D.
OptionA is also wrong because the string generated by grammar is bccccd.
OptionA is also wrong because the string generated by grammar is bccccd.
Question 16 
Which of the following is the most general phasestructured grammar ?
Regular  
Contextsensitive  
Context free  
Syntax tree 
Question 16 Explanation:
→ Phrase structure grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.
→ Most general phase structured grammar is context sensitive grammar.
→ Most general phase structured grammar is context sensitive grammar.
Question 17 
Which of the following strings is in the language defined by grammar
S → 0A
A → 1A/0A/1
S → 0A
A → 1A/0A/1
01100  
00101  
10011  
11111 
Question 17 Explanation:
Question 18 
LL grammar for the language
L = {a^{n} b^{m} c^{n+m}  m≥0, n≥0} is
S → aSc  S_{1} ; S_{1} → bS_{1}c  λ  
S → aSc  S_{1} λ ; S_{1} → bS_{1}c  
S → aSc  S_{1} λ ; S_{1} → bS_{1}c λ  
S → aSc  λ ; S_{1} → bS_{1}c λ 
Question 18 Explanation:
L1 is the language when n=0, m=0.
L1={λ}
L2 is the language when only n=0
L2={bc, bbcc, bbbccc,......}
L3 is the language when only m=0
L3={ ac, aacc, aaaccc, ........}
L4 is the language when n≠0 and m≠0
L4= {abcc, aabbcccc, aaabbbcccccc,...............}
L= {L1 U L2 U L3 U L4}
L= { λ, bc, bbcc, bbbccc,........, ac, aacc, aaaccc,.........., abcc, aabbcccc,aaabbbcccccc,.........}
Option A is incorrect because it does not have any stoping point for condition when m=0 i.e it can't generate strings { ac, aacc, aaaccc, ........}
Option B is incorrect because it does not have any stopping point for condition when n=0 i.e it can't generate strings {bc, bbcc, bbbccc,......}
Option C is correct because it can generate all the strings generated by the language L.
Option D is incorrect because state S1 is unreachable in it. And because of this strings {bc, bbcc, bbbccc,......{abcc, aabbcccc, aaabbbcccccc,...............} can't be generated.
L1={λ}
L2 is the language when only n=0
L2={bc, bbcc, bbbccc,......}
L3 is the language when only m=0
L3={ ac, aacc, aaaccc, ........}
L4 is the language when n≠0 and m≠0
L4= {abcc, aabbcccc, aaabbbcccccc,...............}
L= {L1 U L2 U L3 U L4}
L= { λ, bc, bbcc, bbbccc,........, ac, aacc, aaaccc,.........., abcc, aabbcccc,aaabbbcccccc,.........}
Option A is incorrect because it does not have any stoping point for condition when m=0 i.e it can't generate strings { ac, aacc, aaaccc, ........}
Option B is incorrect because it does not have any stopping point for condition when n=0 i.e it can't generate strings {bc, bbcc, bbbccc,......}
Option C is correct because it can generate all the strings generated by the language L.
Option D is incorrect because state S1 is unreachable in it. And because of this strings {bc, bbcc, bbbccc,......{abcc, aabbcccc, aaabbbcccccc,...............} can't be generated.
Question 19 
The ‘C’ language is
Context free language  
Context sensitive language  
Regular language  
None of the above 
Question 19 Explanation:
C and C++ are context sensitive languages.
Question 20 
The context free grammar for the language
L = {a^{n} b^{m}  n ≤ m + 3, n ≥ 0, m ≥ 0} is
S → aaa A; A → aAb  B, B → Bb  λ  
S → aaaAλ, A → aAb  B, B → Bb  λ  
S → aaaA  aa A  λ, A → aAb  B, B → Bb λ  
S → aaaA  aa A  aA  λ, A →
aAb  B, B → Bb  λ

Question 20 Explanation:
According to given the given language L when
m=0, n<= 3 i.e. L1= { λ, a, aa, aaa}
m=1, n<=4 i.e. L2={ ab, aab, aaab, aaaab}
m=2, n<=5 i.e. L3={abb, aabb, aaabb, aaaabb, aaaaabb} and so on.
Hence L = L1 U L2 U L3 U ...........
L= { λ, a, aa, aaa, ab, aab, aaab, aaaab, abb, aabb, aaabb, aaaabb, aaaabb, .................}
Option(A) is not correct because it can't generate λ.
Option(B) is not correct because it can't generate "a".
Option(C) is not correct because it can't generate "a".
Option(D) is correct because it is generating the language L
.
m=0, n<= 3 i.e. L1= { λ, a, aa, aaa}
m=1, n<=4 i.e. L2={ ab, aab, aaab, aaaab}
m=2, n<=5 i.e. L3={abb, aabb, aaabb, aaaabb, aaaaabb} and so on.
Hence L = L1 U L2 U L3 U ...........
L= { λ, a, aa, aaa, ab, aab, aaab, aaaab, abb, aabb, aaabb, aaaabb, aaaabb, .................}
Option(A) is not correct because it can't generate λ.
Option(B) is not correct because it can't generate "a".
Option(C) is not correct because it can't generate "a".
Option(D) is correct because it is generating the language L
.
Question 21 
Which of the following is the most general phase structured grammar ?
Regular  
Contextsensitive  
Context free  
None of the above 
Question 21 Explanation:
→ Phrase structure grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.
→ Most general phase structured grammar is context sensitive grammar.
→ Most general phase structured grammar is context sensitive grammar.
Question 22 
The language L = {a^{i} b c^{i} │ i >= 0} over the alphabet {a, b, c} is:
a regular language.  
not a deterministic context free language but a context free language.  
recursive and is a deterministic context free language.  
not recursive.

Question 22 Explanation:
→ The given language is Context free language(CFL) because we can push a's onto the top of stack as a's come as input and when a "b" come as input don't push it on the top of stack just change the state and after that when c's come come as input pop one "a" from top of stack for each "c".
→ In this way the given language can be accepted by the deterministic pushdown automata and hence the language is deterministic context free language. And when a language is CFL it is also a recursive language.
Hence the correct answer is option (C)
→ In this way the given language can be accepted by the deterministic pushdown automata and hence the language is deterministic context free language. And when a language is CFL it is also a recursive language.
Hence the correct answer is option (C)
Question 23 
Consider the languages L1 = φ and L2 = {1}. Which one of the following represents L*_{1}∪ L*_{1} L*_{2} ?
{∈}  
{∈, 1}  
ϕ  
1* 
Question 23 Explanation:
As we know, for any regular expression R,
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Rϕ = ϕR=ϕ
So L_{1} L_{2} * = ϕ
and L_{1} * = {ϕ}* = {ϵ}
So L_{1}L_{2}* ∪ L_{1}* = {ϵ}
Question 24 
Which of the following statements is false?
Every contextsensitive language is recursive.  
The set of all languages that are not recursively enumerable is countable.  
The family of recursively enumerable languages is closed under union.  
The families of recursively enumerable and recursive languages are closed under reversal. 
Question 24 Explanation:
Option(A) : it is correct option because L= {a^{n} b^{n} c^{n}} is a context sensitive language and it can also be accepted by the turing machine. Hence every CSL also recursive language.
Option(B): It is incorrect option.
Option(C): Yes it is true that recursively enumerable languages are closed under union.
Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.
NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.
Option(B): It is incorrect option.
Option(C): Yes it is true that recursively enumerable languages are closed under union.
Option(D): It is a correct option because recursively enumerable and recursive languages are closed under reversal.
NOTE: The difference between recursive and recursively enumerable language is that if a language is recursive then there will be definitely a turing machine which will halt and will say whether the string is accepted or not. But if a language is recursively enumerable then the turing machine will halt if the string is accepted but it is not necessary that the turing machine will halt to indicate that the string is not accepted. in this case the user might end up in infinite wait by thinking that turing machine will halt string acceptance process is still in progress.
Question 25 
Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is
{λ, a, b, ab, ba} ∪ {w∈{a, b}*  w > 3}  
{a, b, ab, ba} ∪ {w∈{a, b}*  w > 3}  
{w ∈ { a, b}*  w > 3} ∪ {a, b, ab, ba}  
{λ, a, b, ab, ba} ∪ {w ∈ {a, b}*  w ≥ 3} 
Question 25 Explanation:
Complement of a language L means the complement form of given language L will contain all String except the strings that L contains.
Here L= {aa,bb}
It means complement of L can contain { λ, a, b, ab, ba, aaa, aab, aba, bba,..................}
Hence Option (D) is correct.
Here L= {aa,bb}
It means complement of L can contain { λ, a, b, ab, ba, aaa, aab, aba, bba,..................}
Hence Option (D) is correct.
Question 26 
The family of context sensitive languages is __________ under union and __________ under reversal.
closed, not closed  
not closed, not closed  
closed, closed  
not closed, closed 
Question 26 Explanation:
Context sensitive languages are closed under union, intersection, complement, concatenation, kleene star, ϵfree Homomorphism, substitution( ϵfree), inverse homomorphism, reverse, intersection with regular language.
Hence the correct option is (C)
Hence the correct option is (C)
Question 27 
Match the following:
(a)(i), (b)(ii), (c)(iii), (d)(iv)  
(a)(i), (b)(ii), (c)(iv), (d)(iii)  
(a)(iv), (b)(iii), (c)(ii), (d)(i)
 
(a)(iv), (b)(iii), (c)(i), (d)(ii) 
Question 27 Explanation:
{a^{n} b^{n}n > 0} is a deterministic context free language but not regular because the given language requires a storing device and finite state machine does not contain any storing device. {a^{n} b^{n}n > 0} can be accepted by a pushdown automata by pushing all the a’s on top of stack and when b’s come as input pop one “a” for each “b”.
The given language {a^{n }b^{n} a^{n.  n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly. Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation {an bn an} is context sensitive language but not context free language, the logic is the same as above. SInce for given language can’t be accepted by pushdown automata, so it is not a context free language.}
The given language {a^{n }b^{n} a^{n.  n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly. Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation {an bn an} is context sensitive language but not context free language, the logic is the same as above. SInce for given language can’t be accepted by pushdown automata, so it is not a context free language.}
There are 27 questions to complete.