Step 3: Now, as the string is like therefore, we must start from the NFA of step 1 and finish at the x0y, NFA at step 2. However, we have to insert a from the DFA of step 1 to the DFA of 0-transition step 2. Now, if |x| = 0, then |y| must be 5. So, we can insert a from state to 0-transition A G. Similarly, if |x| = 1, then |y| must be 4. So, we can insert a from state to And in Step 4: 0-transition B H. similar manner, we get: Simplify the RE as much as possible: and draw the equivalent FA. a*b + a*bbb* + a* a*b + a*bbb* + a* ) = a*(b + bbb* + ( ) = a*(b + bb*) + ) [ + = = a*(bb* + xx* x*] [ + = = a*b* x* x*] Equivalent -NFA: Equivalent NFA: Equivalent DFA: Find a string that is represented by the regular expressions and and both r s is represented by either or not r s where and r = a* + b* s = ab* + ba* + b*a + (a*b)* a aba Write down an RE that represents all strings over {0, 1} such that the first and last characters of w are the same and contains at least three 0’s. w w Step 1: The string contains at least three 0’s. 000
Step 3: Now, as the string is like x0y, therefore, we must start from the NFA of step 1 and finish at the NFA at step 2. However, we have to insert a 0-transition from the DFA of step 1 to the DFA of step 2. Now, if |x| = 0, then |y| must be 5. So, we can insert a 0-transition from state A to G. Step 4: Similarly, if |x| = 1, then |y| must be 4. So, we can insert a 0-transition from state B to H. And in similar manner, we get: Simplify the RE as much as possible: a*b + a*bbb* + a* and draw the equivalent FA. a*b + a*bbb* + a* = a*(b + bbb* + ) = a*(b ( + bb*) + ) = a*(bb* + ) [ + xx* = x*] = a*b* [ + x* = x*] Equivalent -NFA: Equivalent NFA: Equivalent DFA: Find a string that is represented by both the regular expressions r and s and is not represented by either r or s where r = a* + b* and s = ab* + ba* + b*a + (a*b)* a aba Write down an RE that represents all strings w over {0, 1} such that the first and last characters of w are the same and w contains at least three 0’s. Step 1: The string contains at least three 0’s. 000
Automata_Study_Guide.docx