# Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been.

Imagine that you are asked to write an algorithm P that takes a regular expression R as input, and returns 1 if and only if L(R) = {0,1}*; otherwise, it should return 0. What would your algorithm do? Please give a carefully explained description of your algorithm.

Note: your algorithm does not need to be "efficient". but it must halt in a finite number of steps(no matter what regular expression R is given as input), and the answer it gives must be correct.

First I drew a DFA that would accept L(R)

Algorithm P

1. Given a regular expression R as input
2. If R={0,1}*, then R=R.1(concatenation of R and 1)
3. Otherwise, R=R.0

My thoughts were that the concatenation of 1 would cause the accept state to be 1 if the input was in {0,1}*, otherwise it would cause the accept state to be 0. I'm not sure what my professor wanted as an answer, should my algorithm have been to build a DFA D that accepts {0,1} *, run input R on D and return a 1 if the DFA accepted R?

-
What do you mean by "the accept state be 1" – Untitled Jun 6 '13 at 7:19

The problem is asking you to determine whether or not a regex accepts every binary string. To do that, your algorithm should traverse the graph of the DFA you built, and if it finds any non-final reachable state, this means that the DFA does not describe $\{0,1\}^*$.

-

I think that you’ve misunderstood the question. You’re supposed to come up with an algorithm that takes as input a regular expression and returns $1$ if that regular expression generates all possible strings of zeros and ones (and nothing else) and returns $0$ otherwise. There are several slightly different conventions for writing regular expressions; I don’t which one you’ve been learning, but I’ll use $\lor$ for or.

• The regular expression $(0\lor 1)^*$ generates the language $\{0,1\}^*$, so your algorithm should return $1$ when the input is $(0\lor 1)^*$.

• The regular expression $(0^*1)^*0^*$ also generates the language $\{0,1\}^*$, so your algorithm should also return $1$ when the input to it is $(0^*1)^*0^*$.

• The regular expression $(0^*1^*)^*$ is yet another input for which your algorithm should return $1$.

• The regular expression $(0\lor 1)(0\lor 1)^*$, on the other hand, generates only the non-empty strings of zeros and ones: it generates the language $\{0,1\}^*\setminus\{\varepsilon\}$, which is not $\{0,1\}^*$, so your algorithm should return $0$ when the input is this regular expression.

Since you weren’t addressing the question that was actually asked, the zero score is appropriate.

Added: As for the question itself, here’s one approach. First, there’s an algorithm for converting a regular expression to a DFA that accepts the language generated by the regular expression. I’m not going to try to describe it here; it’s pretty standard. Then there’s an algorithm that reduces a DFA to an equivalent minimal DFA $\mathscr{M}$, in which all states are reachable. I claim that $\mathscr{M}$ accepts $\{0,1\}^*$ if and only if every state of $\mathscr{M}$ is an acceptor state, something that can be checked algorithmically.

-
@user2357373: What do you mean by the intersection of two DFAs? If you mean the intersection of their languages, that’ll be just the language of the DFA from the regular expression: it won’t be empty unless the reg. exp. generates no words at all. – Brian M. Scott Jun 6 '13 at 7:44
I was just thinking that if the regular expression did not contain 0's or 1's or if it was empty the intersection would be empty. But in your last example it shows that there are cases where that wouldn't work. – user2357373 Jun 6 '13 at 7:54
I was thinking of a DFA that represented the language {0,1}* and trying to work it out in my head, I know that a DFA is not a string of zeros and ones. – user2357373 Jun 6 '13 at 7:56
@user2357373: But you have to be more careful in your use of language: otherwise you’ll confuse others (and very likely yourself as well, eventually if not right away). As for the DFA, don’t forget that just as there can be infinitely many different reg. exprs. that generate the same language, there can be infinitely many different DFAs that accept it. – Brian M. Scott Jun 6 '13 at 7:58
Sorry, in class we were taught algorithms to perform operations such as union and intersection on DFA's and I should have been more clear. As for your algorithm did you mean to convert the regular expression to an NFA, then if you convert an NFA to a DFA aren't all states reachable? – user2357373 Jun 6 '13 at 8:04