CODEWITHSUNDEEP
state-machine
kubiej21
kubiej21

Reputation: 698

State machine, set of strings?

I am working on a homework assignment that deals with state machines. I understand how they operate, but there are a couple aspects of this particular question that I am not understanding.

Let L be the set of strings over {a,b} ending with the substring abba.
a. Build a DFA that accepts L.
b. Build an NFA with 6 transitions that accepts L.

How can I incorporate L into a state machine? I am completely lost with part b, but I feel that once I understand part a, b shouldn't be too difficult.

Upvotes: 1

Views: 421

Answers (2)

billjamesdev
billjamesdev

Reputation: 14640

Let me try this:

Node 0:
a -> node 1   <-- This means, "if the next character is a, then go to node 1"
b -> node 0
END -> error
Node 1:
a -> node 1
b -> node 2
END -> error
Node 2:
a -> node 1
b -> node 3
END -> error
Node 3:
a -> node 4
b -> node 0
END -> error
Node 4:
END -> Success!
a -> node 1
b -> node 0

I believe that should do it. Each node has 3 possible arrows out of it, for an a, b, or end of string (END). Each input that's part of "abbaEND" leads to the next node and finally success, and each input that isn't part of "abbaEND" takes you back to the node appropriate. Basically, if it's an a, it treats it as the start of another "abba" block, and if it's a b, it assumes "abba" is coming next. An early END is a failure. That should be your DFA map.

So, using any string of a's and b's as input... this DFA should only end in Success! if the string ends in "abba", and should end in error for any other string.

Upvotes: 0

Sean McSomething
Sean McSomething

Reputation: 6517

Let's back up a bit. By convention, "L" is used to define a "language" - in this context a set (possibly infinite) of strings that meet some definition. When playing with finite automata, you're concerned with what strings are "accepted" by the machine and which ones are "rejected" & generally you want to accept all the strings in a given language & reject those that are not in it (another way of looking at the problem is that you can define a language as the set of all strings accepted by a machine - they're equivalent).

The first question is an exercise in building a DFA that accepts L - that is that, given any string that ends in "aaba", it accepts & given strings that don't end in "abba" it rejects. Your confusion seems to come from thinking that L somehow is "part of" your machine; at best you encode a description of L into your machine.

The second question is asking you to do the same thing with a NFA, with the additional restriction that it only has 6 transitions.

Upvotes: 2

Related Questions