In this article, we are going to learn about the basic and advanced Interview questions and answers related to computer science. These types of questions have a high probability that can be asked in any computer science-related exam like in your University Exams, Competition exams, Hackathons, and Technical Quiz competitions. so be prepared and read all the questions in a proper manner.

#### Which of the following is false?

1. The languages accepted by FAs are regular languages
2. Every DFA is an NFA
3. There are some NFAs for which no DFA can be constructed
4. If L is accepted by an NFA with (ε) transition

Answer - (3) Every DFA is an NFA

#### Which of the following is not true?

1. The set of languages accepted by deterministic and nondeterministic PDAs are not equal
2. L = {WCW^(r)|w in (0 + 1)* & c ∉ {0,1} } can be accepted by a deterministic PDA
3. L = {ww^(r)|w in (0 + 1)*} can be accepted by a deterministic PDA
4. L{0^n 1^n | n >= 0} can be accepted by a deterministic PDA

Answer - (3) L = {ww^(r)|w in (0 + 1)*} can be accepted by a deterministic PDA

#### Let r1 = ab*c* & r2 = (a * b ∨ c)* and r3 = (a ∨ b ∨ c)* Then which of the following is true

1. w = ac belongs to L(r2) and L(r3) but not L(r1)
2. w = ac belongs to L(r3) only
3. w = ac belongs to L(r1), L(r2) and L(r3)
4. w = ac belongs to L(r1) and L(r3) but not L(r2)

Answer - (4) w = ac belongs to L(r1) and L(r3) but not L(r2)

#### Which of the following statements are true?

The complement of a language is always regular.
The intersection of regular languages is regular.
The complement of a regular language is regular.

1. (i) & (ii) only
2. (ii) & (iii) only
3. (i) & (iii) only
4. All of the above

Answer - (2) (ii) & (iii) only

#### Which of the following is not true?

1. CFLs are closed under union and concatenation.
2. Regular languages are closed under union and intersection.
3. CFLs are not closed under intersection and complementation.
4. If L is a CFL and R is a regular set then L ∩ R is not a CFL.

Answer - (4)  If L is a CFL and R is a regular set then L ∩ R is not a CFL

#### Context-free languages and regular languages are both closed under the operations (s) of

Union
Intersection
Concatenation

1. (i) and (ii) only
2. (ii) and (iii) only
3. (i) and (iii) only
4. all of the above

Answer - (3) (i) and (iii) only

#### Let ∑ = {a, b}  r1 = a(a ∨ b)*  r2 = b(a ∨ b)* Which of the following is true?

1. L(r1) = L(r2) = ∑*
2. L(r1) ⋂ L(r2) = {λ}
3. L(r1) ⋃ L(r2) = ∑*
4. L(r1) ⋃ L(r2) ⋃ {λ} = ∑*

Answer - (4) L(r1) ⋃ L(r2) ⋃ {λ} = ∑*

#### Which of the following statements are true?

abcd ∈ L((b*a*)*(d*c*)*)
abcd ∈ L((d*c*b*a*)*)
abcd ∈ L((a*b*a*c*d*)*)

1. (i) and (iii) only
2. (ii) and (iii) only
3. (i) and (ii) only
4. all of the above

Answer - (4) all of the above

#### Which of the following are regular languages?

The language {WIW ∈ {a, b}*, W has an odd number of b's}
The language {WIW ∈ {a, b}*, W has an even number of b's}
The language {WIW ∈ {a, b}*, W has an even number of b's an odd number of a's}

1. (i) and (ii) only
2. (i) only
3. (ii) only
4. all of the above

Answer - (4) all of the above

#### Which of the following regular expression corresponds to the language of all strings over the alphabet {a, b} that contains exactly two a'S

aa
ab*a
b*ab*a

1. (i) and (ii) only
2. (ii) and (iii) only
3. (i) and (iii) only
4. None of these

Answer - (4) None of these

#### Which of the following regular expression corresponds to the language of all strings over the alphabet {a, b} that do not end with ab.

1. (a + b)* (aa + ba + bb)
2. (a + b)* (aa + ba + bb) + a + b + λ
3. b* ab* a
4. b* aa b*

Answer - (2) (a + b)* (aa + ba + bb) + a + b + λ

#### What is regular expression corresponding to the language of strings of even lengths over the alphabet of {a,b}

1. (aa + bb + ba + ab)*
2. (aa + bb)*
3. (ab + bb + ba)*
4. a*b*a*b*

Answer - (1) (aa + bb + ba + ab)*

1. 2
2. 3
3. 4
4. 5

Answer - (2) 3

1. 20
2. 9
3. 7
4. 15

Answer - (1) 20

#### Which of the following definitions below generates the same language as L where L = {x^n y^n| n >= 1}?

E -> xEy | xy
xy | (x+ y+)
x+ y+

1. (i) only
2. (i) and (ii)
3. (ii) and (iii)
4. (i) and (iii) only

Answer - (1) (i) only

#### Let X = {0, 1}, L = X* and R = {0^n 1^n/n>0} then the language L ⋃ R and R respectively

1. Regular, Regular
2. None regular, Regular
3. Regular, Not regular
4. Not regular, Not regular

Answer - (3) Regular, Not regular

1. 2
2. 3
3. 4
4. 5

Answer - (2) 3

#### Which of the following identifies are correct?

1. rs* = rss*
2. (r*s*) = (r + s)*
3. (r + s)* = r* + s*
4. (r*s*)* = (r + s)*

Answer - (4) (r*s*)* = (r + s)*

#### Let L1 and L2 be regular sets defined over alphabet ∑*. Mark the false statement

1. L1 ∪ L2 is regular
2. L1 ∩ L2 is not regular
3. ∑* - L1 is regular
4. L1* is regular

Answer - (2) L1 ∩ L2 is not regular

#### Which of the following languages are context free

L1 = {a^mb^mc^n | m >= 1 and n >= 1}
L2 = {a^mb^mc^n | n >= m}
L3 = {a^mb^mc^m | m >= 1}

1. only L1
2. L2 and L3
3. only L2
4. L3

Answer - (1) only L1

Note - More questions and answers will be added time to time