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