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.

A
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?

A
II only
B
III only
C
I only
D
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.
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?

A
L1 is context-free but not regular and L2 is context-free.
B
Neither L1 nor L2 is context-free.
C
L1 is regular and L2 is context-free.
D
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.
Question 4
Which of the following statements is/are TRUE?
A
Every subset of a recursively enumerable language is recursive.
B
If a language L and its complement L' are both recursively enumerable, then L must be recursive.
C
Complement of a context-free language must be recursive.
D
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.
Question 5
Which of the following statements is/are CORRECT?
A
The intersection of two regular languages is regular.
B
The intersection of two context-free languages is context-free.
C
The intersection of two recursive languages is recursive.
D
The intersection of two recursively enumerable languages is recursively enumerable.
Question 6
The number of productions of the following grammar is
E → E+T | T
T → T*F | F
F → E| id 
A
5
B
3
C
6
D
4
Question 6 Explanation: 
Total 6 productions are there.
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id
Question 7
What is the highest type number which can be applied to the following grammar?
S→Aa, A→Ba, B→abc 
A
Type 0
B
Type 1
C
Type 2
D
Type 3
Question 7 Explanation: 
The given grammar is left linear grammar which is also a regular grammar. Hence the highest type number which can be applied to the following grammar is Type 3 which is notation for regular grammar.
Question 8
Consider the following statements.
1. The intersection of two context-free languages is always context-free.
2. The super-set of a context-free language is never regular.
3. The subset of a decidable language is always decidable.
4. Let Σ ≡ {a, b, c} . Let L ⊆ Σ be the language of all strings in which either the number of occurrences of a is the same as the number of occurrences of b OR the number of occurrences of b is the same as the number of occurrences of c. Then, L is not context-free.
Which of the above statements are true?
A
Only (1)
B
Only (1) and (2)
C
Only (1),(2) and (3)
D
Only (4)
E
None of (1), (2), (3), (4) are true
Question 9
Consider the context-free grammar below (s denotes the empty string, alphabet is {a, b}):
S → ε|aSb|bSa|SS.
What language does it generate?
A
(ab) + (ba)
B
(abba) +(baab)
C
(aabb) + (bbaa)
D
Strings of the form anbn or bnan, n any positive integer
E
Strings with equal numbers of a and b
Question 10
If every production is of the form where or of the form , then the grammer is said to be of:
A
Type 3
B
Type 1
C
Type 0
D
Type 2
Question 11
Which of the following represents the language over the set A={a,b} consisting of all words beginning with one or more a’s and followed by the same number of b’s?
A
L= {a,ab,ab2,...}
B
L= {ambn:m,m>0,n>0}
C
L= {ambm:m>0}
D
L= {bmabn:m0,n0}
Question 11 Explanation: 
→In the option C, ambm:m>0, For a given “m” value always it generates one or more “a” s followed by Same number of “b” s.
→Example :
m=1 ⇒ ab
m=2⇒ aabb and so on.
Question 12
The language which is generated by the grammar S aSa | bSb | a | b over the alphabet {a,b} is the set of
A
Strings that begin and end with the same symbol
B
All odd and even length palindromes
C
All odd length palindromes
D
All even length palindromes
Question 12 Explanation: 
The grammar generates {a, b, aaa, aba, bab, bbb, aaaaa, aabaa, …}
So the grammar generate odd length palindrome.
Question 13
A grammar is defined as
A→ BC
B→ x | Bx
C→ B | D
D→ y | Ey
E→ z
The non-terminal alphabet of the grammar is
A
{A,B,C,D,E}
B
{B,C,D,E}
C
{A,B,C,D,E,x,y,z}
D
{x,y,z}
Question 13 Explanation: 
Since A,B,C,D,E all derive something in grammar so {A,B,C,D,E} all are non terminals, also by default we represent non terminal with capital letters.
Question 14
The language L = {ai b ci │ i >= 0} over the alphabet {a, b, c} is:
A
a regular language.
B
not a deterministic context free language but a context free language.
C
recursive and is a deterministic context free language.
D
not recursive.
Question 14 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)
Question 15
Which of the following is true for the language {ap] p is a prime]
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, bt accepted by Turing machine
Question 15 Explanation: 
The sequence of p is not in arithmetice progression form due to which it not context and not regular but can be accepted by turing machine.
Question 16
The language L={0i21i | i≥0 } over the alphabet {0.1, 2} is:
A
Not recursive
B
Is recursive and is a deterministic CFL
C
Is a regular language
D
Is not a deterministic CFL but a CFL
Question 16 Explanation: 
The given language is DCFL and hence recursive. First we will push 0’s in the stack and when we will see 2 then just read it and then pop 0’s corresponding to one 1.
Question 17
Consider the following grammar :
S→0A|0BB
A→00A| λ
B→1B|11C
C→B
Which language does this grammar generate?
A
L(00) * 0+(11)*1)
B
L(0(11)* + 1(00)*)
C
L((00)*0)
D
L(0(11) *1)
Question 17 Explanation: 
Option 1 is incorrect because every string generated by given grammar will contain only 0's and given option is generating string containing 1's also. Option 2 is incorrect because it can't generate "000". Option 3 is correct because it generates string same as given grammar do. Option 4 is incorrect because every string generated by given grammar will contain only 0's and given option is generating string containing 1's also.
Question 18

Consider the following grammars :



Which of the following is correct w.r.t. the above grammars?
A
G1 and G3 are equivalent
B
G2 and G3 are equivalent
C
G2 and G4 are equivalent
D
G3 and G4 are equivalent
Question 19

Consider the following language families :

L1 = The context – free language

L2 = The context – sensitive language

L3 = The recursively enumerable language

L4 = The recursive language

Which one of the following options is correct?
A
L1 ⊆ L2 ⊆ L3 ⊆ L4
B
L2 ⊆ L1 ⊆ L3 ⊆ L4
C
L1 ⊆ L2 ⊆ L4 ⊆ L3
D
L2 ⊆ L1 ⊆ L4 ⊆ L3
Question 19 Explanation: 
Question 20
Consider the language L={n>2} on Σ={a,b}. Which ch one of the following generates the language L?
A
S →aA |a,A → aAb |b
B
S → aaA |λ, A → aAb|λ
C
S → aaaA |a, A → aAb|λ
D
S → aaaA |λ, A → aAb|λ
Question 20 Explanation: 
Option1 is incorrect because it can generate “a” where n=1. so given condition(n>2) is violated. Option 2 is incorrect because it can generate “null string”. so given condition(n>2) is violated. Option3 is incorrect because it can generate “a” where n=1. so given condition(n>2) is violated. Option4 is correct because it can generate strings “ab,aaa, aaaab…...” where nn>2. so it is the correct option.
Question 21
Which of the following statements is FALSE?
A
For every Non-deterministic PDA there exists an equivalent DPDA
B
For every Non-deterministic TM there exists an equivalent deterministic TM
C
For every regular expression there exists an equivalent NFA
D
For every NFA there exists an equivalent DFA
Question 21 Explanation: 
A) False because NPDA is more powerful than DPDA.
B) True because Non deterministic TM has the same power as Deterministic TM.
C) True because regular expressions have the same power as NFA.
D) True because NFA and DFA are equivalent in power.
There are 21 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access