A machine is represented by states Q, input alphabet Σ, transition function δ,…
2025
A machine is represented by states Q, input alphabet Σ, transition function δ, initial state q₀ and final state F. The machine accepts all the strings over Σ = {a, b}, which start and ended with any combination of all alphabet and abb works/lies as substring in all the strings to be accepted.
For the above specified passage, which of the following represents the regular expression?
- A.
(a+b)*aab
- B.
aba(a+b)*
- C.
b(a+b)*b(a+b)*a(a+b)*
- D.
(a+b)*abb(a+b)*
Attempted by 117 students.
Show answer & explanation
Correct answer: D
Answer: (a+b)*abb(a+b)*
Reasoning: The language is all strings over {a,b} that contain the contiguous substring abb. To allow any characters before and after that substring, use (a+b)* as prefix and suffix.
Allow any prefix: (a+b)*
Require the substring: abb
Allow any suffix: (a+b)*
Combining these gives (a+b)*abb(a+b)*. Examples of accepted strings: abb, aabb, babb, abbaab.
Why the other expressions are incorrect:
(a+b)*aab matches strings that end with "aab", which does not ensure the substring "abb" appears.
aba(a+b)* forces strings to start with "aba", which is unnecessary and does not guarantee "abb" is present.
b(a+b)*b(a+b)*a(a+b)* requires occurrences of b, then later b, then later a, but does not require the contiguous substring "abb".
A video solution is available for this question — log in and enroll to watch it.