This lab should be done individually, although you may certainly discuss your progress with your neighbors.
A finite state machine is said to accept a given input string if the input takes the machine from the start state, indicated in these diagrams by a triangle, to an accepting (or final) state, indicated by a double border.
We will be dealing with relatively simple finite state automata that are easily drawn by hand. If you wish, you may use JFLAP, a graphical tool for experimenting with concepts from automata theory, to check your work. You can access JFLAP on-line at www.jflap.org. Download the first version listed, "JFLAP_Thin.jar". (Click here for a simple "cheat sheet" on using JFLAP.)
Write down answers to each of the numbered questions below. First, try answering these questions without building the machines in JFLAP. Feel free to use JFLAP to check your answers.
1001? Will it accept
1010? Will it accept
Regular expressions provide another way of describing the sets of
strings that are "accepted" by a finite state machine, i.e.,
for which the finite state machine will halt in an "accept" state.
Binary strings are just sequences of 0's and 1's, such as,
An empty string has no items in it,
i.e., has a length of 0.
Regular expressions can be built using three different operators:
Concatenation (followed-by) - This is expressed by placing two symbols
(or other regular expressions) adjacent to each other. For example,
01 represents the string of length 2 composed of a zero
followed by a one;
1000001 represents the string of length 7 composed of a
one, followed by five zeros, followed by a one.
Union (or) - This is expressed with the
(1 + 0)
1. The expression
11, while the
Star - The star operator matches any number (including zero) of
repetitions of the starred item. For example
101010, etc. Parentheses
are used to group operators.
00101100? Does it match the string