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

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 7

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 8

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

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 9 Explanation:

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

Question 10

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

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 12

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

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

Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is

A	{λ, a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
B	{a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
C	{w ∈ { a, b}* \| \|w\| > 3} ∪ {a, b, ab, ba}
D	{λ, a, b, ab, ba} ∪ {w ∈ {a, b}* \| \|w\| ≥ 3}

Theory-of-ComputationLanguages-and-GrammarsUGC NET CS 2016 Aug- paper-3

Question 14 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.

Question 15

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

Question 16

Which of the following statement is false?

A	Every regular language is also a context free language
B	Every non deterministic turing machine can be converted to an equivalent deterministic Turing machine
C	Every subset of recursively enumerable set is recursive
D	Every NFA can b converted into equivalent DFA

Theory-of-ComputationLanguages-and-GrammarsCIL 2020

Question 16 Explanation:

A is true.
B is true because non deterministic Turing machines and deterministic Turing machines are equal in power.
C is false, because there are some recursively enumerable sets which are not recursive.
D is true, because NFA and DFA are equal in power.

Question 17

The language generated by following grammar is:
S --> aSa | bSb | ε

A	Even length palindrome
B	a^m b^n n>=0, m>=0
C	Odd length palindrome
D	a^n b^m n>=1, m>=1

Theory-of-ComputationLanguages-and-GrammarsCIL 2020

Question 17 Explanation:

The strings generated by the grammar is
{ε,aa,bb,abba,baab,aaaa,bbbb,aaaaaa,bbbbbb,aabbaa,abbbba,baaaab,bbaabb,........}.
So the given grammar generates all even length palindromes.

Question 18

The language {a^m bⁿ c^m+n | m, n>=1} is:

A	Regular
B	Type 0 but context sensitive
C	Context free but not regular
D	Context sensitive but not context free

Theory-of-ComputationLanguages-and-GrammarsCIL 2020

Question 18 Explanation:

The given language is not regular because there are infinite dependencies between a, b and c.
But the given language is context free, because the given language can be identified using stack. First push a’s in the stack, then push b,s in the stack, now on looking c’s pop b,s and then on looking c’s pop a’s. If nothing is left on the stack and c’s are finished then the string is accepted else not accepted.

Question 19

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

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 20 Explanation:

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

Question 21

Consider L=L₁ ∩ L₂ where L₁ = {0^m 1^m 20ⁿ 1ⁿ| m,n ≥0} L₂ = {0^m 1ⁿ 2^k | m,n,k ≥0} Then, the language L is

A	recursively enumerable but not context free
B	regular
C	Context free but not regular
D	Not recursive

Theory-of-ComputationLanguages-and-GrammarsUGC NET JRF November 2020 Paper-2

Question 21 Explanation:

L1 will first contain 0’s followed by an equal number of 1’s. After that there will be a single 2 which will again be followed by 0’s and equal number of 1’s. I.e. L1 ={ 2, 012, 00112, 20011, 01201, 0011201, 0120011, 001120011,........}
L2 = { epsilon, 0,1,2,01,12, 012, 00112, 20011, 01201, 0011201, 0120011, 001120011,........}
L=L1 ∩ L2 = { 2, 012. 00112, 0001112,.......}
L1 ∩ L2 = { 0^m1^m2 | m>=0}, which is a context free language but not regular language. Hence option 3 is correct.

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	{λ, a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
B	{a, b, ab, ba} ∪ {w∈{a, b}* \| \|w\| > 3}
C	{w ∈ { a, b}* \| \|w\| > 3} ∪ {a, b, ab, ba}
D	{λ, a, b, ab, ba} ∪ {w ∈ {a, b}* \| \|w\| ≥ 3}