LanguagesandGrammars
Question 1 
(a) Given a set
S = {x there is an xblock of 5's in the decimal expansion of π}
(Note: xblock is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.
 (i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive
(b) Given that a language L_{1} is regular and that the language L_{1} ∪ L_{2} is regular, is the language L_{2} always regular? Prove your answer.
Theory Explanation. 
Question 2 
Consider the language L = {a^{n} n≥0} ∪ {a^{n}b^{n} n≥0} and the following statements.
 I. L is deterministic contextfree.
II. L is contextfree but not deterministic contextfree.
III. L is not LL(k) for any k.
Which of the above statements is/are TRUE?
II only  
III only  
I only  
I and III only 
We can make DPDA for this.
L is not LL(k) for any “k” look aheads. The reason is the language is a union of two languages which have common prefixes. For example strings {aa, aabb, aaa, aaabbb,….} present in language. Hence the LL(k) parser cannot parse it by using any lookahead “k” symbols.
Question 3 
Consider the following languages.
 L_{1} = {wxyx  w,x,y ∈ (0 + 1)^{+}}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
L_{1} is contextfree but not regular and L_{2} is contextfree.  
Neither L_{1} nor L_{2} is contextfree.
 
L_{1} is regular and L_{2} is contextfree.
 
L_{1} is contextfree but L_{2} is not contextfree. 
So it is equivalent to
(a+b)^{+} a (a+b)^{+} a + (a+b)^{+} b (a+b)^{+} b
L_{2} is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 4 
Every subset of a recursively enumerable language is recursive.
 
If a language L and its complement L' are both recursively enumerable, then L must be recursive.  
Complement of a contextfree language must be recursive.  
If L1 and L2 are regular, then L1 ∩ L2 must be deterministic contextfree 
If L and L(complement) both are recursively enumerable then L must be recursive. It is a theorem.
Every CFL is CSL and CSL is closed under complement so complement of CFL must be CSL and every CSL is recursive. Thus the complement of CFL must be CSL, hence it must be recursive also.
If L1 and L2 are regular then their intersection must be regular, as regular languages are closed under intersection, so L1 intersection L2 must be regular, hence it must be DCFL, since every regular is also a DCFL.
Question 5 
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 6 
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} 
Hence it is a^{m}b^{n}  n>m, m>=0
Question 7 
all palindromes  
all odd length palindromes  
strings that begin and end with the same symbol  
all even length palindromes 
Question 8 
S → Aa
A → Ba
B → abc
Type 0  
Type 1  
Type 2  
Type 3 
Question 9 
S → SS
S → (S)
S → ε
10  
15  
12  
16 
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 10 
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 11 
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) 
It is the infinite set of all possible strings of all possible lengths over Σ(input set) excluding ʎ(empty string).
Question 12 
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 
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 
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} 
→ We are computing all possible strings using 2^{n} formula. Where n is number of strings.
Question 14 
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 
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 15 
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 16 
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. 
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 17 
S→d/bA
A→d/ccA
bccddd  
aabccd  
ababccd  
abbbd  
None of the above 
OptionA is also wrong because the string generated by grammar is bccccd.
Question 18 
Regular  
Contextsensitive  
Context free  
Syntax tree 
→ Most general phase structured grammar is context sensitive grammar.
Question 19 
S → 0A
A → 1A/0A/1
01100  
00101  
10011  
11111 
Question 20 
10  
45  
56  
55 
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