CODEWITHSUNDEEP
finite-automata
Muhammad Sami
Muhammad Sami

Reputation: 550

Finite Automata string not ending with ba

Question: Build an FA that accepts only those words that do not end with ba. I want to Draw DFA for this problem but I don't understand I to do it please help me to draw this

Upvotes: 3

Views: 14088

Answers (3)

yousaf23
yousaf23

Reputation: 66

Steps:

  1. Draw DFA which ends with "ba".
  2. Invert the states i.e.
  3. Make the final states, non final.
  4. Non final states, final states

IMAGE: DFA of strings not ending with "ba":

enter image description here

Upvotes: 5

sabeen kanwal
sabeen kanwal

Reputation: 607

RE for a language that do not end on ba is (a+b)*(aa+bb+ab)

here language either ends on aa or bb or ab

enter image description here

to make DFA from RE you can use this hope it would proved helpful for you https://cyberzhg.github.io/toolbox/nfa2dfa

enter image description here

in this given DFA ..it is accepting strings with length 2 or greater than 2 but not ending on ba

Upvotes: 1

Patrick87
Patrick87

Reputation: 28302

We need to keep track of whether we have seen substrings of ba and if we see the whole thing, make sure we're not in an accepting state at the time.

----->(q0)--b-->(q1)--a-->(q2)

Here, (q0) is accepting, (q1) is accepting and (q2) is not accepting. (q0) corresponds to having seen no part of the string ba, state (q1) to having seen the first symbol, and (q2) to having seen the whole thing. The missing transitions should therefore be:

  • q0 to q0 on symbol a, since if we haven't started seeing ba, a is no help; we needed a b
  • q1 to q1 on symbol b, since if we see b we have always at least seen the first symbol in ba
  • q2 to q0 on symbol a and to q1 on symbol b, for the above reasons.

The whole DFA looks like this:

                /--|--b----\
                b  |       |
                |  V       |
----->(q0)--b-->(q1)--a-->(q2)
      |  ^                 |
      a  |                 |
      \--|-----------------/

Upvotes: 0

Related Questions