Which of the following languages can be recognized by Non-Deterministic Finite…
2024
Which of the following languages can be recognized by Non-Deterministic Finite Automata (NFA) but cannot be recognized by Deterministic Finite Automata (DFA)?
(A) L₁={w∈{0, 1}* | the length of w is even}
(B) L₂={w∈{0, 1}* | the length of w is odd}
(C) L₃={w∈{0, 1}* | all 0's come before all 1's in w}
(D) L₄={w∈{0, 1}* | w contains an equal number of 0's and 1's}
(E) L₅={w∈{0, 1}* | all 1's come before all 0's in w}
Choose the correct answer from the options given below:
Answer: A. (A) (B) (C) and (E) Only — (A) L₁: Strings of even length ✔ Regular language → Recognizable by both DFA and NFA (B) L₂: Strings of odd length ✔ Regular language → Recognizable by both…
- A.
(A) (B) (C) and (E) Only
- B.
(B) and (C) Only
- C.
(C) and (D) Only
- D.
(D) and (E) Only.
Attempted by 68 students.
Show answer & explanation
Correct answer: A
(A) L₁: Strings of even length
✔ Regular language → Recognizable by both DFA and NFA(B) L₂: Strings of odd length
✔ Regular language → Recognizable by both DFA and NFA(C) L₃: All 0’s come before all 1’s (0*1*)
✔ Regular language → Recognizable by both DFA and NFA(D) L₄: Equal number of 0’s and 1’s
❌ Not a regular language → Recognizable by neither DFA nor NFA(E) L₅: All 1’s come before all 0’s (1*0*)
✔ Regular language → Recognizable by both DFA and NFA
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2