Discussion
Consider the following deterministic finite automaton (DFA) defined over the alphabet, \(\Sigma = \{a, b\}\). Identify which of the following language(s) is/are accepted by the given DFA.
Answer: C
The DFA accepts the set of all strings ending with the pattern \(bab\).
Read the states left to right as remembering how much of bab the input has just seen: the start state (nothing useful), state 2 (last symbol b), state 3 (last two symbols ba) and the accepting state 4 (last three symbols bab). Each transition keeps this meaning: from 4, an a leaves the string ending in ba (state 3) and a b leaves it ending in b (state 2); from 3, an a gives baa, which ends with no useful prefix (start).
So a string is accepted exactly when it ends in bab. 'Containing bab' is wrong because baba contains bab but ends in state 3. 'Not containing aba' fails on ab, which does not contain aba but is rejected. 'Even number of b's' fails on bb, which has two b's but is rejected.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development