0
$\begingroup$

Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring.

She wrote that regular expression: $0^*\cup 0^*1(00^*1)^*0^*$. I have nothing against that but after the lecture I tried to solve that problem on my own and came up with that expression: $0^*\cup0^*(100^*)^*0^*$.

Is that true? It appears to me that I can even get rid of $0^*$ at the end of expression and simplify as $0^*\cup0^*(100^*)^*$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The regexp attributed to your instructor can't generate $10101$, for example. Your result appears to be fine. There are many regular expressions that correspond to the same language. Welcome to the site. $\endgroup$
    – Rick Decker
    Feb 10, 2020 at 18:31
  • $\begingroup$ @RickDecker since I am new to the site , I couldn't write the expression the expression wrote properly. At the end there is zero to kleene star , so I guees it can now generate 10101 . Thanks for the comment and welcoming :) $\endgroup$
    – no one ever
    Feb 10, 2020 at 18:42
  • $\begingroup$ For later use, the asterisk (or star, or $*$) has a special meaning here, so to get one to appear as it should, one way is to enclose a mathematical expression in dollar signs, like [dollar sign][asterisk][dollar sign] $\endgroup$
    – Rick Decker
    Feb 10, 2020 at 18:52
  • $\begingroup$ @RickDecker I will keep that in mind :) $\endgroup$
    – no one ever
    Feb 10, 2020 at 20:40
  • $\begingroup$ Your solution cannot generate for example 0000001. It insists that a 1 must be followed by zeroes. $\endgroup$
    – gnasher729
    Feb 10, 2020 at 21:44

0

Reset to default