CODEWITHSUNDEEP
computer-sciencefinite-automatadfanfaautomata-theory
Tashfeen Choudhury
Tashfeen Choudhury

Reputation: 13

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

Upvotes: 1

Views: 5132

Answers (1)

RBarryYoung
RBarryYoung

Reputation: 56735

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.

Upvotes: 1

Related Questions