topic - solutions adda

Languages-and-Grammars

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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.

(b) Given that a language L₁ is regular and that the language L₁ ∪ L₂ is regular, is the language L₂ always regular? Prove your answer.

A	Theory Explanation.

Theory-of-ComputationLanguages-and-GrammarsGATE 1994

Question 2

Consider the following languages.

₁

⁺

₂

Which one of the following is TRUE?

A	L₁ is context-free but not regular and L₂ is context-free.
B	Neither L₁ nor L₂ is context-free.
C	L₁ is regular and L₂ is context-free.
D	L₁ is context-free but L₂ is not context-free.

Theory-of-ComputationLanguages-and-GrammarsGATE 2020Video-Explanation

Question 2 Explanation:

L₁ 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
L₂ is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.

Question 3

Consider the language L = {aⁿ| n≥0} ∪ {aⁿbⁿ| n≥0} and the following statements.

Which of the above statements is/are TRUE?

A	II only
B	III only
C	I only
D	I and III only

Theory-of-ComputationLanguages-and-GrammarsGATE 2020Video-Explanation

Question 3 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 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

Theory-of-ComputationLanguages-and-GrammarsGATE 2022Video-Explanation

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.

Theory-of-ComputationLanguages-and-GrammarsGATE 2023Video-Explanation

Question 6

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,ab²,...}
B	L= {a^mbⁿ:m,m>0,n>0}
C	L= {a^mb^m:m>0}
D	L= {b^mabⁿ:m0,n0}

Theory-of-ComputationLanguages-and-GrammarsCIL Part - B

Question 6 Explanation:

→In the option C, a^mb^m: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 7

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

Theory-of-ComputationLanguages-and-GrammarsCIL Part - B

Question 8

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 aⁿbⁿ or bⁿaⁿ, n any positive integer
E	Strings with equal numbers of a and b

Theory-of-ComputationLanguages-and-GrammarsTIFR PHD CS & SS 2020

Question 9

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

Theory-of-ComputationLanguages-and-GrammarsTIFR PHD CS & SS 2020

Question 10

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

Theory-of-ComputationLanguages-and-GrammarsTNPSC-2012-Polytechnic-CS

Question 10 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 11

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

Theory-of-ComputationLanguages-and-GrammarsTNPSC-2012-Polytechnic-CS

Question 11 Explanation:

Total 6 productions are there.
E->E+T
E->T
T->T*F
T->F
F->(E)
F->id

Question 12

The language L = {aⁱ b cⁱ │ 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.

Theory-of-ComputationLanguages-and-GrammarsUGC NET CS 2017 Nov- paper-3

Question 12 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 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}

Theory-of-ComputationLanguages-and-GrammarsISRO CS 2020Video-Explanation

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

Theory-of-ComputationLanguages-and-GrammarsISRO CS 2020Video-Explanation

Question 14 Explanation:

The grammar generates {a, b, aaa, aba, bab, bbb, aaaaa, aabaa, …}
So the grammar generate odd length palindrome.

Question 15

The language L={0ⁱ21ⁱ| 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

Theory-of-ComputationLanguages-and-GrammarsAPPSC-2016-DL-CS

Question 15 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 16

Which of the following is true for the language {a^p] 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

Theory-of-ComputationLanguages-and-GrammarsAPPSC-2016-DL-CS

Question 16 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 17

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\|λ

Theory-of-ComputationLanguages-and-GrammarsUGC-NET DEC-2019 Part-2

Question 17 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 18

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	L₁ ⊆ L₂ ⊆ L₃ ⊆ L₄
B	L₂ ⊆ L₁ ⊆ L₃ ⊆ L₄
C	L₁ ⊆ L₂ ⊆ L₄ ⊆ L₃
D	L_{2_{⊆ L₁ ⊆ L₄ ⊆ L₃}}

Theory-of-ComputationLanguages-and-GrammarsUGC-NET DEC-2019 Part-2

Question 18 Explanation:

Question 19

Consider the following grammars :

Which of the following is correct w.r.t. the above grammars?

A	G₁ and G₃ are equivalent
B	G₂ and G₃ are equivalent
C	G₂ and G₄are equivalent
D	G₃ and G₄ are equivalent

Theory-of-ComputationLanguages-and-GrammarsUGC-NET DEC-2019 Part-2

Question 20

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)

Theory-of-ComputationLanguages-and-GrammarsUGC-NET DEC-2019 Part-2

Question 20 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 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

Theory-of-ComputationLanguages-and-GrammarsHCU PHD CS MAY 2019

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

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

A	S →aA \|a,A → aAb \|b
B	S → aaA \|λ, A → aAb\|λ
C	S → aaaA \|a, A → aAb\|λ
D	S → aaaA \|λ, A → aAb\|λ