Algorithm for a regular expression

Question

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$?

Answer 1

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\}^*$.

Answer 2

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.