Your intuition about starting and ending with the same symbol is correct. This is a good example of why the unbounded memory rule of thumb is not perfect.
The NFA you described recognizes
(01)* ∪ (10)*
All strings in the above language will begin and end with different symbols and have only even lengths. (Balanced means not only equal in number but that they nest properly, e.g., )()()( and ())( have equal numbers of left- and right-parentheses but not in balance.) The empty string ε does belong to the language, and your NFA — but not your regular expression — correctly accepts it. The language from Sipser’s lecture has strings of odd length as well, the shortest being 0 and 1 that an equal number (namely, zero) of 01 and 10 substrings.
Your regular expression is close. It looks like HN’s markdown formatting ate your Kleene stars. Always account for the empty string, and in your case it does need to appear explicitly.
ε ∪ 0 ∪ 1 ∪ 0(0 ∪ 1)*0 ∪ 1(0 ∪ 1)*1
Because this is a simple enough language, I suggest building a DFA rather than an NFA. You know that your automaton will have two branches: one for strings beginning with 0 and the other for those that begin with 1. That accounts for three states so far, and your initial state q0 has both of its transitions defined. Let’s say that q1 is the state after reading the initial 0. (Remember that you can interpret each state in a finite automaton’s transition graph as “I have read …”) When you’re in q1 and read a 0, where do you go? When you’re in q1 and read a 1, where do you go? You’ll know you completed this branch when you have defined 0 and 1 transitions for all its states. Then move on to completing the branch for strings that begin with 1. The intuition is it ought to have similar structure to the first branch. Finally, label your final or accept states. Always remember to account for the empty string!
What’s really interesting is the NFA you defined has, after conversion to DFA and minimization, almost the same structure as the correct DFA: the only difference is which are accept states.
The NFA you described recognizes
All strings in the above language will begin and end with different symbols and have only even lengths. (Balanced means not only equal in number but that they nest properly, e.g., )()()( and ())( have equal numbers of left- and right-parentheses but not in balance.) The empty string ε does belong to the language, and your NFA — but not your regular expression — correctly accepts it. The language from Sipser’s lecture has strings of odd length as well, the shortest being 0 and 1 that an equal number (namely, zero) of 01 and 10 substrings.Your regular expression is close. It looks like HN’s markdown formatting ate your Kleene stars. Always account for the empty string, and in your case it does need to appear explicitly.
Because this is a simple enough language, I suggest building a DFA rather than an NFA. You know that your automaton will have two branches: one for strings beginning with 0 and the other for those that begin with 1. That accounts for three states so far, and your initial state q0 has both of its transitions defined. Let’s say that q1 is the state after reading the initial 0. (Remember that you can interpret each state in a finite automaton’s transition graph as “I have read …”) When you’re in q1 and read a 0, where do you go? When you’re in q1 and read a 1, where do you go? You’ll know you completed this branch when you have defined 0 and 1 transitions for all its states. Then move on to completing the branch for strings that begin with 1. The intuition is it ought to have similar structure to the first branch. Finally, label your final or accept states. Always remember to account for the empty string!What’s really interesting is the NFA you defined has, after conversion to DFA and minimization, almost the same structure as the correct DFA: the only difference is which are accept states.