Computer Science Interview Questions and Answers

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

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 is 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 and 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)*

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

1. 2
2. 3
3. 4
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?

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

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

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 from time to time