Write down a regular expression for the language = {w {a, | does not contain an L b}* w occurrence of ab}. Step 1: should not contain So, the RE for be or However, the RE for cannot w ab. w a*b, ab* a*b*. may be , or Note that the RE includes the REs , and w a*, b*, b*a*. b*a* a* b*. Step 2: Therefore, the final RE is b*a*. Find and draw the minimum-state DFA for the DFA below: Transition Table of the given DFA: State a b 1 2 3 → 2 4 5 3 6 7 * 4 4 5 5 6 7 * 6 4 5 * 7 6 7 Minimization of the given DFA: Step 1: Separating final and non-final states, we get the following groups: {1, 2, 3, 5} {4, 6, 7} Step 2: From the group {4, 6, 7}, we separate the group {4, 6} as they move to the non-final group {1, 2, 3, 5} for the input symbol b. {1, 2, 3, 5} {4, 6} {7} Step 3: From the group {1, 2, 3, 5}, we separate the group {3, 5} as they move to the final group {7} for the input symbol b. {1, 2} {3, 5} {4, 6} {7} Step 4: From the group {1, 2}, we separate the elements into two groups as for the symbol state 1 a, remains in the same group whereas state 2 moves to the group {4, 6}. {1} {2} {3, 5} {4, 6} {7} Diagram of the minimum-state DFA: Find the regular expression equivalent to the DFA in the following figure: Inputs States 0 1 →* Q1 Q2 Q1 Q2 Q3 Q2
Write down a regular expression for the language L = {w {a, b}* | w does not contain an occurrence of ab}. Step 1: w should not contain ab. So, the RE for w cannot be a*b, ab* or a*b*. However, the RE for w may be , a*, b*, or b*a*. Note that the RE b*a* includes the REs , a* and b*. Step 2: Therefore, the final RE is b*a*. Find and draw the minimum-state DFA for the DFA below: Transition Table of the given DFA: State a b → 1 2 3 2 4 5 3 6 7 * 4 4 5 5 6 7 * 6 4 5 * 7 6 7 Minimization of the given DFA: Step 1: Separating final and non-final states, we get the following groups: {1, 2, 3, 5} {4, 6, 7} Step 2: From the group {4, 6, 7}, we separate the group {4, 6} as they move to the non-final group {1, 2, 3, 5} for the input symbol b. {1, 2, 3, 5} {4, 6} {7} Step 3: From the group {1, 2, 3, 5}, we separate the group {3, 5} as they move to the final group {7} for the input symbol b. {1, 2} {3, 5} {4, 6} {7} Step 4: From the group {1, 2}, we separate the elements into two groups as for the symbol a, state 1 remains in the same group whereas state 2 moves to the group {4, 6}. {1} {2} {3, 5} {4, 6} {7} Diagram of the minimum-state DFA: Find the regular expression equivalent to the DFA in the following figure: States Inputs 0 1 →* Q1 Q1 Q2 Q2 Q3 Q2
Automata_Study_Guide.docx