0
$\begingroup$

I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't accept 0100 for example or 010101 etc, also if I write a finite automata for this how do I prove its correctness ?

$\endgroup$
  • 3
    $\begingroup$ I would produce an automaton and then convert it to a regular expression. $\endgroup$ – David Richerby Oct 28 '14 at 12:17
  • $\begingroup$ Please restrict yourself to one question per post; you are posing two very different ones. David gives you a good hint; the usual proof strategy is induction. See here for an introduction to such proofs for grammars; since NFA are basically the same as (right-)regular grammars, the principles carry over. $\endgroup$ – Raphael Oct 28 '14 at 13:35
1
$\begingroup$

You can write a regular expression directly:

  • First ignore the odd number of zeroes. You can easily write an expression for this modified language, based on the fact that you can choose to particularize the first occurence of $10$ (namely $0^*1^*10(0+1)^*$ is a valid expression).
  • Now you want to modify the first part ($0^*1^*$) and the second part $(0+1)^*$ to take into account the odd number of zeroes. Since these two parts have to agree (have the same parity of zeroes) there are two disjoint cases: either you have even numbers of $0$'s before and after the $10$ pattern, or an odd numbers:

    1. To have an even number of $0$'s before the pattern, simply write $(00)^*1^*$. For an even number after the pattern, this is simply an expression for a word with an even number of zeroes: $1^*(01^*0)^*1^*$ (each $0$ has a friend). Together, this gives you the expression: $(00)^*1^*\ 10\ 1^*(01^*0)^*1^*$.

    2. To have odd numbers, you can re-use modified versions of the expressions in 1.: Before the pattern, you add a first $0$ in front: $0(00)^*1^*$; After the pattern, you need a first $0$ but also $1$'s in the middle: $1^*01^*(01^*0)^*1^*$. Together: $ 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$.

Globally, you have the disjunction of the two cases:

$$(00)^*1^*\ 10\ 1^*(01^*0)^*1^* + 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$$

This is not meant to be the smallest possible expression, but at least it shows how you can construct one. For instance, you can factorize the common parts to obtain $$ (00)^*(1^*10+01^*101^*0)1^*(01^*0)^*1^*.$$

$\endgroup$

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.