Languages-and-Grammars
Question 1 |
(a) Given a set
S = {x| there is an x-block of 5's in the decimal expansion of π}
(Note: x-block 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 L1 is regular and that the language L1 ∪ L2 is regular, is the language L2 always regular? Prove your answer.
Theory Explanation. |
Question 2 |
Consider the language L = {an| n≥0} ∪ {anbn| n≥0} and the following statements.
- I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
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 |
Question 2 Explanation:
L is DCFL.
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.
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.
- L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?
L1 is context-free but not regular and L2 is context-free. | |
Neither L1 nor L2 is context-free.
| |
L1 is regular and L2 is context-free.
| |
L1 is context-free but L2 is not context-free. |
Question 3 Explanation:
L1 is regular. y can be expanded and w can also expanded. So x can be either "a" or "b".
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
So it is equivalent to
(a+b)+ a (a+b)+ a + (a+b)+ b (a+b)+ b
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Question 4 |
Which of the following statements is/are TRUE?
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 context-free language must be recursive. | |
If L1 and L2 are regular, then L1 ∩ L2 must be deterministic context-free |
Question 4 Explanation:
Every subset of recursively enumerable need not be recursive. For example (a+b)* is a universal language and regular. Every language over alphabet {a,b} is subset of (a+b)*. This language is regular so it is recursively enumerable also and so many languages are known to be non-recursive which are definitely subset of (a+b)*. Thus every subset of recursively enumerable need not be recursive.
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.
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 |
Given the following statements:
S1 : Every context-sensitive language L is recursive
S2 : There exists a recursive language that is not context-sensitive
Which statements are true?
S1 : Every context-sensitive language L is recursive
S2 : There exists a recursive language that is not context-sensitive
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 5 Explanation:
According to the Chomsky hierarchy, both the statements are correct.
Question 6 |
Identify the language generated by the following grammar
S -> AB
A -> aAb|ϵ
B -> bB| b
S -> AB
A -> aAb|ϵ
B -> bB| b
{ambn | n>=m, m>0} | |
{ambn | n>=m, m>=0} | |
{ambn | n>m, m>0} | |
{ambn | n>m, m>=0} |
Question 6 Explanation:
The language generated by given grammar is - L={b,bb,abb,abbb,ababb}
Hence it is ambn | n>m, m>=0
Hence it is ambn | n>m, m>=0
Question 7 |
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 7 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 8 |
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 8 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 9 |
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 9 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 10 |
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 10 Explanation:
Question 11 |
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 11 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 12 |
Which of the definitions generates the same languages as L, where
L={ xn yn , n>=1 }
i. E→ xEy |xy
ii.xy|x + x yy +
iii. x + y +
L={ xn yn , n>=1 }
i. E→ xEy |xy
ii.xy|x + 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
Definition-1: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 xy|x + x yy + gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 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 definition-3 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
Definition-1: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 xy|x + x yy + gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 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 definition-3 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} |
Question 13 Explanation:
→ All possible strings of length 2 over Σ = {a,b} = 4(aa,ab,ba,bb}.
→ We are computing all possible strings using 2n formula. Where n is number of strings.
→ We are computing all possible strings using 2n formula. Where n is number of strings.
Question 14 |
Which of the definitions generates the same languages as L, where
L={ x n y n , n>=1 }
i. E→ xEy |xy
ii.xy|x + x yy +
iii. x + y +
L={ x n y n , n>=1 }
i. E→ xEy |xy
ii.xy|x + x yy +
iii. x + y +
i only | |
i and ii only | |
ii and iii only | |
ii only |
Question 14 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
Definition-1 :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 xy|x + x yy + gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 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 definition-3 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
Definition-1 :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 xy|x + x yy + gives xy, xxyy , xxxxyy , xxyyyyy and so on
The definition-2 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 definition-3 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 → XRX|S, S → aTbTa, T → XTX|Xϵ X → a|b
The strings which are not in L(G) are:
ab,ba,aab
| |
abb,aabab
| |
a,b,aa
| |
a,b,ϵ
|
Question 15 Explanation:
We can’t generate the strings “a” and “b” because the Starting symbol is R→ XRX|S.
Question 16 |
Which of the following is FALSE?
The grammar S→aS|aSbS|∈, where S is the only non-terminal 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 top-down parser. |
Question 16 Explanation:
Option-A: TRUE: S is non terminal symbol, ∈ is the null string, is ambiguous.
Option-B: FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
Option-C: 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.
Option-D: TRUE: Recursive descent parser is a top-down parser
Option-B: FALSE: An unambiguous grammar has same leftmost and rightmost derivation.
Option-C: 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.
Option-D: TRUE: Recursive descent parser is a top-down parser
Question 17 |
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 17 Explanation:
Here, there is no terminal symbol ‘a’, so the answer never be option B,C,D.
Option-A is also wrong because the string generated by grammar is bccccd.
Option-A is also wrong because the string generated by grammar is bccccd.
Question 18 |
Which of the following is the most general phase-structured grammar ?
Regular | |
Context-sensitive | |
Context free | |
Syntax tree |
Question 18 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 19 |
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 19 Explanation:
Question 20 |
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 20 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
There are 20 questions to complete.