Consider the regular language L = (111 + 11111)*. The minimum number o...
The finite state automata is :
Thus, option (D) is correct.
Please comment below if you find anything wrong in the above post.
View all questions of this test
Consider the regular language L = (111 + 11111)*. The minimum number o...
Solution:
To find the minimum number of states in any DFA accepting this language, we need to construct a DFA for the given regular language L = (111 11111)* and minimize it using the standard DFA minimization algorithm.
Constructing DFA for L = (111 11111)*
Step 1: Start with the initial state q0.
Step 2: For each input symbol 1, create a new state and transition from the current state to the new state on input 1.
Step 3: Assume all the new states are final states.
Step 4: The final DFA will be:
q0 ---1---> q1 ---1---> q2 ---1---> q3 ---1---> q4 ---1---> q5
---1---> q6 ---1---> q7 ---1---> q8 ---1---> q9 ---1---> q10
---ε---> q11
Step 5: Mark all pairs of states (q0, q11), (q1, q6), (q2, q7), (q3, q8), (q4, q9), (q5, q10) as distinguishable.
Step 6: Repeat step 5 until no more pairs can be marked as distinguishable.
Step 7: The minimized DFA will be:
q0 ---1---> q1 ---1---> q2 ---1---> q3 ---1---> q4 ---1---> q5
---1---> q6
---ε---> q11
Step 8: The minimized DFA has 9 states, which is the minimum number of states in any DFA accepting the given regular language L.
Therefore, the correct answer is option D.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).