computer-sciencefinite-automatadfanfaautomata-theory

Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter


I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA, but can not find a solution for a proper NFA after multiple tries.

The solution of my DFA for the language provided above:

The solution of my DFA for the language provided above:

My attempts for the NFA are down below. I apologize for my messy handwriting but these were just rough works that I was drawing out on the go.

My first attempt:

My first attempt at solving the NFA

My second attempt:

My second attempt at solving the NFA

My third attempt:

My third attempt at solving the NFA


Solution

  • There's only three words, so just make three parallel paths for your NFA, using a transition function like the following:

    Input State Input Symbol Output States
    [start] a [a.b], [a.bb]
    [start] b [b.aa]
    [a.b] b [ab#]
    [a.bb] b [ab.b]
    [ab.b] b [abb#]
    [b.aa] a [ba.a]
    [ba.a] a [baa#]

    Here, state names are in brackets ([..]) and state names that end with "#" are terminal.

    Generally it's considered easier to make an NFA than a DFA, so the usual method is to first make an NFA and then make the DFA by modifying the NFA by changing multiple output states to a single intermediate state.

    If you followed this method for the above NFA, then the resulting DFA would look something like this (I have appended an "*" to the intermediate state names):

    Input State Input Symbol Output State
    [start] a [a.b*]
    [start] b [b.aa]
    [a.b*] b [ab.*]
    [ab.*] (e) [ab#]
    [ab.*] b [abb.*]
    [abb.*] (e) [abb#]
    [b.aa] a [ba.a]
    [ba.a] a [baa#]

    I've been a bit loose about all of the empty symbol/end-of-input transitons to terminal states. If you need me to fill al of them in, them I can do that.