CODEWITHSUNDEEP
automatadfa
silverlight
silverlight

Reputation: 45

Deterministic Finite Automata

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:

  • Construct a Deterministic Finite Automata (DFA) diagram?
  • Find the regular expression for the DFA?

    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.

    Upvotes: 1

    Views: 1055

    • Answers (2)

    Somya Taneja
    Somya Taneja

    Reputation: 1

    We can get two possibilities here- 1) String starts with 0 and ends with 1 => [0(0|1)*1] 2) Strings staring with 1 and ending with 0 => [1(0|1)*0] Also from rejected strings we know that minimum length would be 2.

    Therefore final expression would be [0(0|1)*1]|[1(0|1)*0] NFA would be something like this

    NFA for given language

    Upvotes: 0

    Tharindu Rusira
    Tharindu Rusira

    Reputation: 691

    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

    Upvotes: 2

    Related Questions