I am new to automata theory. This question below is for practice:
Let there be a language that is made of words that start and end with different symbols and have the alphabet {0,1}. For example, 001, 10110101010100, 10 and 01 are all accepted. But 101, 1, 0, and 1010001101 are rejected.
How do I:
I tried to post an image of the DFA I drew, but I need 10 reputations to post images unfortunately, which I do not yet have.
To answer this question, I think it's easier to identify the regular expression first.
Regular Expression
1(1|0)*0 | 0(1|0)*1
(* denotes Kleene's star operation)
Now we convert this regular expression into an equivalent finite automata.
Constructing a DFA
You can design the NFA-∧(or NFA-ε in some texts) easily using Thompson constructors[1] for a given language(regex) which is then converted into an NFA without lambda transitions. This NFA can then be mapped to an equivalent DFA using subset construction method. [2]
If you want, you can further reduce this DFA to obtain a minimal DFA which is unique for a given regular language. (Myhill-Nerode theorem) [3]
Regex → NFA-∧ → NFA → DFA → DFA(minimal), This is the standard procedure.
[1]http://en.wikipedia.org/wiki/Thompson%27s_construction_algorithm
[2] http://www.cs.nuim.ie/~jpower/Courses/Previous/parsing/node9.html
[3]http://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem