5. Now do (but don\'t submit yet) the following additional problems about DFAs:
ID: 3587942 • Letter: 5
Question
5. Now do (but don't submit yet) the following additional problems about DFAs: start 4 Figure 1 Additional Problem 5-01 Answer all of the following questions for the DFA shown in Figure 1 o (e.g.for the string aabbba would answer 1,2,3,3,3,3,4 NO Does it accept the string Does it accept the string a Does it accept the string b Does it accept the string alb Does it accept the string ba Does it accept the string aa Does it accept the string bb Does it accept the string aaa Does it accept the string aab Does it accept the string aba Does it accept the string abb Does it accept the string baa Does it accept the string bab Does it accept the string bba Does it accept the string bbb Is the language of this DFA finite or infinite?? Additional Problem 5-02 Give a regular expression that represents the language accepted by the DFA in figure 1 o Additional Problem 5-03 Give a formal definition of the DFA shown in Figure 1 (i.e. describe it as a 5-tuple) (Be very careful with your parentheses and curly braces!!!) oExplanation / Answer
5.
5-01
As the initial state is also the final state, Yes, it accepts ^.
1 YES
No, a is not accepted as it will be at node 2 after accepting a.
1,2 NO
No, b is also not accepted as it goes to the dead state after receiving b.
1,4 NO
No, ab is also not accepted as it goes to the dead state after receiving b at 2nd node.
1,2,4 NO
No, ba is also not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4 NO
Yes, aa is accepted as it goes to the 3rd node after receiving two a’s.
1,2,3 YES
No, bb is not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4 NO
No, aaa is not accepted as it goes to the dead state from 3rd node after receiving the third a.
1,2,3,4 NO
Yes, aab is accepted as it remains at the 3rd node after receiving b.
1,2,3,4,4 YES
No, aba is not accepted as it goes to the dead state after receiving b at 2nd node.
1,2,4,4 NO
No, abb is not accepted as it goes to the dead state after receiving b at 2nd node.
1,2,4,4 NO
No, baa is also not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4,4 NO
No, bab is also not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4,4 NO
No, bba is also not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4,4 NO
No, bbb is also not accepted as it goes to the dead state after receiving b at 1st node.
1,4,4,4 NO
The language of the DFA is infinite as it accepts the strings with any number of b’s after 2 a’s.
Eg. It accepts aab, aabb, aabbb and so on.
5-02
Since, receiving “b” on initial state leads to dead node, it must start with a.
Also, in the node 2, receiving “b” leads to dead state and receiving “a” leads to final state.
From the above two lines, it is clear that the string must start with two a’s.
In the final state i.e. the 3rd node, on receiving “a” leads to dead node whereas on receiving, it still remains at the final state.
Hence, Regular expression will be
^ (empty string) U aab*
5-03
M = (Q, , , q0, F)
a
b
1
2
4
2
3
4
3
4
3
4
4
4
a
b
1
2
4
2
3
4
3
4
3
4
4
4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.