Question
Download Solution PDFThe minimum possible number of states of a deterministic finite automation that accepts the regular language L = {w1aw2 | w1, w2 ϵ {a, b}*, |w1| = 2, |w2| ≥ 3} is ________.
Answer (Detailed Solution Below) 8
Detailed Solution
Download Solution PDFGiven language is: L = {w1aw2 | w1, w2 ϵ {a, b}*, |w1| = 2, |w2| ≥ 3}
Regular expression: (a+b) (a+b) a (a+b) (a+b) (a+b)(a+b)*
Minimum length string that is possible = (a+b) (a+b) a (a+b) (a+b) (a+b)
This string has minimum length 6. For these 7 states are needed and one trap state. So, total 8 states are needed.
DFA for given language is
Last updated on Jan 8, 2025
-> GATE CS 2025 Admit Card has been released on 7th January 2025.
-> The exam will be conducted on 1st February 2025 in 2 shifts.
-> Candidates applying for the GATE CE must satisfy the GATE Eligibility Criteria.
-> The candidates should have BTech (Computer Science). Candidates preparing for the exam can refer to the GATE CS Important Questions to improve their preparation.
-> Candidates must check their performance with the help of the GATE CS mock tests and GATE CS previous year papers for the GATE 2025 Exam.