0
$\begingroup$

I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):

(0+1+ϵ)4+(11100+ϵ)r(0011100r)*(00111+ϵ)

r=11+(110+ϵ)s(0110s)*(011+ϵ)

s=(0+10)*(1+ϵ)

How should I convert this into an NFA? Please explain the steps behind it as well!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ cs.stackexchange.com/q/137007/755 $\endgroup$
    – D.W. ♦
    Commented Mar 25, 2021 at 19:09
  • $\begingroup$ It would be better for you to show more independence when doing your homework. $\endgroup$
    – Yuval Filmus
    Commented Mar 28, 2021 at 14:07
  • $\begingroup$ Where is your regular expression taken from? $\endgroup$
    – Yuval Filmus
    Commented Mar 28, 2021 at 14:10
  • $\begingroup$ @YuvalFilmus this regular was provided to me by my friend who is doing this assignment with me. And I have just asked a conceptual question regarding converting a regular expression to an NFA, which is something I cannot understand well. So, could you please answer my question? $\endgroup$
    – Jayajit
    Commented Mar 29, 2021 at 17:33
  • $\begingroup$ cs.stackexchange.com/a/13606/755 $\endgroup$
    – D.W. ♦
    Commented Dec 7, 2022 at 19:14

1 Answer 1

Reset to default
2
$\begingroup$

What you need is the Berry-Sethi algorithm, constructing the Glushkov's automaton.

However, for your problem, I'd consider constructing directly a DFA with $10 = \begin{pmatrix}5\\2\end{pmatrix}$ states corresponding to words of size 5 containing exactly two zeros, and a sink state (and maybe some other states for the begining of the reading).

The Glushkov's automaton on your regular expression will be very big.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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