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?

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

**Answer – **(3) Every DFA is an NFA

## Which of the following is not true?

- The set of languages accepted by deterministic and nondeterministic PDAs is not equal
- L = {WCW^(r)|w in (0 + 1)* & c ∉ {0,1} } can be accepted by a deterministic PDA
- L = {ww^(r)|w in (0 + 1)*} can be accepted by a deterministic PDA
- 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

- w = ac belongs to L(r2) and L(r3) but not L(r1)
- w = ac belongs to L(r3) only
- w = ac belongs to L(r1), L(r2) and L(r3)
- 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 is true?

The complement of a language is always regular.

The intersection of regular languages is regular.

The complement of a regular language is regular.

- (i) & (ii) only
- (ii) & (iii) only
- (i) & (iii) only
- All of the above

**Answer – **(2) (ii) & (iii) only

## Which of the following is not true?

- CFLs are closed under union and concatenation.
- Regular languages are closed under union and intersection.
- CFLs are not closed under intersection and complementation.
- 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

- (i) and (ii) only
- (ii) and (iii) only
- (i) and (iii) only
- 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?

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

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

## Which of the following statements is true?

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

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

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

- (i) and (iii) only
- (ii) and (iii) only
- (i) and (ii) only
- 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 and an odd number of a’s}

- (i) and (ii) only
- (i) only
- (ii) only
- 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

- (i) and (ii) only
- (ii) and (iii) only
- (i) and (iii) only
- 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?

- (a + b)* (aa + ba + bb)
- (a + b)* (aa + ba + bb) + a + b + λ
- b* ab* a
- 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}

- (aa + bb + ba + ab)*
- (aa + bb)*
- (ab + bb + ba)*
- a*b*a*b*

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

## How many minimum numbers of states will be there in the DFA accepting all strings (over the alphabet {a,b}) that do not contain two consecutive a’s

- 2
- 3
- 4
- 5

**Answer – **(2) 3

## How many minimum a number of states are required in the DFA (over the alphabet {a, b}) accepting all the strings with the number of a’S divisible by 4 and number of b’S divisible by 5?

- 20
- 9
- 7
- 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+

- (i) only
- (i) and (ii)
- (ii) and (iii)
- (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

- Regular, Regular
- None regular, Regular
- Regular, Not regular
- Not regular, Not regular

**Answer – **(3) Regular, Not regular

## How many states does the DFA constructed for The set of all strings ending with “00”, have?

- 2
- 3
- 4
- 5

**Answer – **(2) 3

## Which of the following identifies are correct?

- rs* = rss*
- (r*s*) = (r + s)*
- (r + s)* = r* + s*
- (r*s*)* = (r + s)*

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

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

- L1 ∪ L2 is regular
- L1 ∩ L2 is not regular
- ∑* – L1 is regular
- 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}

- only L1
- L2 and L3
- only L2
- L3

**Answer – **(1) only L1

**Note** – More questions and answers will be added from time to time