0
$\begingroup$

How can I show that the language {$w \epsilon$ {$0,1$}$^{*}:$ the word $w$ contains neither the (sub)string $000$ nor $11$} is regular without using a DFA? (Using the closure properties)

$\endgroup$
  • 1
    $\begingroup$ Some possibilities: (1) Find a regular expression for $L$. (2) Find a regular grammar that generates $L$. (3) Show that the condition of the Myhill-Nerode theorem is satisfied. $\endgroup$ – Brian M. Scott Dec 15 '13 at 0:20
  • $\begingroup$ A ok! To use the closure properties do I have to find a regular expression for L1={the word w contains the (sub)string 000} and L2={the word w contains the (sub)string 11}? So knowing that L1 and L2 are regular, the union is regular and the complement? $\endgroup$ – Mary Star Dec 15 '13 at 0:24
  • 1
    $\begingroup$ You could do it that way. Regular grammars for $L_1$ and $L_2$ (and then their union) would also be easy to write. $\endgroup$ – Brian M. Scott Dec 15 '13 at 0:28
  • $\begingroup$ This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. $\endgroup$ – Carl Mummert Dec 15 '13 at 1:37
  • $\begingroup$ @BrianM.Scott We could also find the regular expressions for L1={the word w does not contain the (sub)string 000} and L2={the word w does not contain the (sub)string 11} and then their union, right? Would the expression be for L1 be (0U10)* and for L2 (1U01U110)* $\endgroup$ – Mary Star Dec 15 '13 at 16:56
2
$\begingroup$

Let $L$ be the language in question. Here are four possibilities:

  1. Come up with a regular expression that generates $L$.
  2. Come up with a regular grammar that generates $L$.
  3. Show that $L$ satisfies the condition of the Myhill-Nerode theorem.
  4. Show that $L$ is the complement of a regular language over $\{0,1\}$.

The first two are self-explanatory, I think, though not necessarily easy. The third is actually fairly straightforward if you’ve seen the Myhill-Nerode theorem: words in that contain $000$ or $11$ are in one equivalence class, and the other classes can be identified by looking at the last one or two symbols of the word. The fourth is also straightforward, since it’s not hard to write a regular expressionss or grammar for the complement of $L$.

$\endgroup$
  • $\begingroup$ Since I have to use the closure properties, I think I could use the first, the second or the forth way.. For the first and the second could you tell me how to find these regular expressions/grammars? For the forth way, do I have to show that the language {$w \epsilon$ {0,1}$^{*}$: the word w contains the (sub)string 000 and 11} is regular? $\endgroup$ – Mary Star Dec 15 '13 at 1:13
  • 1
    $\begingroup$ @Mary: The first two approaches really are a bit messy. It wouldn’t be hard to construct a DFA, and there are algorithms to transform a DFA into a regular expression or a regular grammar, but I think that you’re better off using (4): it’s much easier. Yes, you want to show that $$\{w\in\{0,1\}^*:w\text{ contains }000\text{ or }11\}$$ is regular. (Note that that’s or, not and.) It’s pretty easy to write a regular expression for that language. $\endgroup$ – Brian M. Scott Dec 15 '13 at 1:20
  • $\begingroup$ Because I am not familiar enough with the regular expressions yet,could you tell me if that what I think is right? Is the regular expression for that language {$(000)^{*},(11)^{*}$} ? $\endgroup$ – Mary Star Dec 15 '13 at 9:04
  • $\begingroup$ @Mary: No, that would just give you all strings of the forms $0^{3n}$ and $1^{2n}$, strings consisting of a multiple of $3$ zeroes or an even number of ones. A regular expression for the $L_1$ of your earlier comment is $(0\lor 1)^*000(0\lor 1)^*$. (There are various notations for regular expressions; in another common one that’s $(0+1)^*000(0+1)^*$.) This gives any string, followed by $000$, followed by any string, and that exactly describes the words in $L_1$. $L_2$ has a very similar description. $\endgroup$ – Brian M. Scott Dec 15 '13 at 21:38

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.