0
$\begingroup$

How can we make a DFA for given condition in title from alphabets {0,1} (binary).

What can be the regular expression for this?

My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'm wrong and help find the correct expression and it's DFA.

$\endgroup$
2
$\begingroup$

You probably want to substitute $a$ with $1$ and $b$ with $0$ but apart from that your solution is correct.

Finding an equivalent NFA is easy with Thompson, Glushkov etc. From that you can derive an DFA via powerset construction. However, for this short expression you also can just write the DFA down. Imagine the states as storage what the last 3 symbols were, and accept if the third last was a 1, i.e. name the states 000 to 111 where 000 is the initial state and all states with a leading 1 are accepting. A transition is just a shift-left with the last read symbol on the right, i.e. $\delta(abc, d) = bcd$, with $a,b,c,d \in \{0,1\}$.

$\endgroup$
  • $\begingroup$ Oops , my bad on the mixup of 1,0 and a,b. I tried what you said but it created a very big and complex DFA. I tried to design DFA directly from the regular expression as i don't know other methods you suggested . uploading photo of DFA now please check it and correct if i'm wrong. $\endgroup$ – WizWarrior Mar 11 '18 at 17:16
1
$\begingroup$

Your regular expression is correct.

For a DFA, in this case it's easier to define it than to draw it. Formally, defining a DFA means choosing an alphabet, a state set, a start state, an accepting set, and a transition function.

Alphabet: $\Sigma = \{0,1\}$ as specified.

State set: The states are ordered triples $(x,y,z)$ where $x$, $y$, and $z$ are either 0, 1, or Null. These represent the last three symbols seen.

Start state: Start in state (Null, Null, Null). We haven't seen any symbols yet, with Null meaning "no symbol seen yet".

Accepting set: A state $(x, y, z)$ is accepting if $x$ is 1. That is, we accept if the third symbol from the end was a 1.

Transition function: If you're in state $(x, y, z)$ and you see symbol $s$, you transition into state $(y, z, s)$.

This fully defines the DFA, without needing to draw it out (which is more complicated for this question).

$\endgroup$
-1
$\begingroup$

enter image description here

Check this out , it's not neat but it will get the work done. Correct me if i'm wrong in this DFA.

$\endgroup$
  • $\begingroup$ If you make $q_6$ accepting, I think it is correct. I still encourage to draw my solution as it should give you more insights why it is correct. (It seems to be the same as your DFA, but double check for yourself for understanding what is going on) $\endgroup$ – ttnick Mar 11 '18 at 17:39
  • $\begingroup$ It's wrong...it will not accept for the language 00100 for the dfa given in the answer $\endgroup$ – Faizan Sep 11 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.