Quick Quiz #1
Just in case you've forgotten the notation, though, here are some reminders:
- Each solid dot represents a state in the finite state automata.
- Any unlisted transitions are assumed to go to a "dead state", or, if you prefer, stall the machine in a non-accepting state.
- A circle around a state means that it is an accepting state for the machine.
- And, for review, the regular expression that the FSA above represents is (00)*(11)*
What is the correct regular expression for the following FSA?
spaces are for readability
A. (11 | 110)* 0 is Correct! This is actually the regular expression which was originally used to derive this
FSA during a recent class I attended. But, there's another valid expression. Have you found it yet?
B.1(11)*(0|00) is incorrect. In fact, if you look closely, none of the strings it generates are correct. All
valid strings from the FSA shown have an even number of 1's. This one requires an odd number, and doesn't allow
0's to occur all of the places they would from the provided FSA.
C.(1 | 0)* is incorrect. While it does match all of the strings in the language of the FSA,
it matches many many more. In fact, this expression will take any string that can be constructed from the alphabet
{1,0}.
D.(0 | (11 (011 | 11)* (0 | 00)) is correct. It is a much more complex regular expression than
is necessary for the task, but it does correctly match the same strings as the FSA accepts. Have you found the
simpler version yet?
E.(0 | (11 (011 | 11)* 0) is not correct. Nice try. This expression doesn't find 1100, which
is one of the acceptable strings according to the FSA.
F.(0 | 110 | 11 | 1100 | 11110) is not correct. While it does include several of the shorter
strings which this FSA accepts, this FSA recognizes strings of nearly any length, which are not represented by
this expression.
Comments
You're weird.
Posted by: Anonymous | February 15, 2001 11:29 AM
Note that answer number 3, contrary to the comments, is not correct, in that it it not even a valid regular expression.
(0 | (11 (011 | 11)* (0 | 00))
...is missing a trailing ")", and thus is not correct for any state diagram.
Thanks, The RegExp Pedant
Posted by: Anonymous | February 15, 2001 08:11 PM
You twit. You go on and on about anal parenthesis matching, but you can't tell the difference between "it" and "is" in your post.
Thbbbt.
Posted by: Anonymous | February 15, 2001 08:12 PM
Oh yeah? Well, your mother likes Hot Grits.
Posted by: Anonymous | February 15, 2001 08:13 PM
Oh lighten up, it's not like you couldn't tell what he meant. Let's see you be perfect all the time. On the other hand, why does he want us to do his homework?
Posted by: Anonymous | February 15, 2001 08:14 PM
First Post!
Posted by: Anonymous | February 15, 2001 08:15 PM
Damn.
Posted by: Anonymous | February 15, 2001 08:15 PM
Twasn't a homework assignment. A better question would be whether you'd like to write something like this yourself. Needn't be out of coursework (though this was a spinoff of a cs507 lecture from spring 200), but that's certainly reasonable. Try not to steal a professor's homework/quiz questions, though, as I didn't here.
Posted by: bp | February 15, 2001 09:38 PM
Thanks. I'm amazed at how many people I showed that to and how none of them had noticed that up until now.
Besides that, why do I get the feeling you were talking to yourself? I guess the Slashdot effect might be about more than just snowing a server with traffic as soon as its discovered.
Posted by: bp | February 15, 2001 09:44 PM