Java Finite State Automata and Regular Expressions This project explores the imp

Question

Java

Finite State Automata and Regular Expressions

This project explores the implementation of finite state machines and has two parts.

1) Write a program that starts by asking the user to describe a finite state automaton. You then display a regular expression describing the strings accepted by this FSA.

2) Write a program that takes a regular expression as an input and describes the FSA associated with the expression.

For both parts, allow the user to enter a bit string and have your program determine whether it is accepted or rejected by their FSA or regular expression.

Explanation / Answer

1.

...
...
typedef enum {ON, OFF} bulb_state;
typedef enum {TURN_ON, TURN_OFF} switch_command;
...
...
bulb_state state;
switch_command command;
switch (state)
{
case ON:
if (command == TURN_ON)
{
}
else if (command == TURN_OFF)
{
state = OFF;
}
break;
case OFF:
if (command == TURN_ON)
{
state = ON;
}
else if (command == TURN_OFF)
{
}
break;
default:
assert(0);
}

If code such as this looks familiar, it's hardly surprising. Many of us write state machines in our code without even noticing. Most of the state machines we write are "implicit", in the sense that there isn't a single switch statement that handles the whole machine, but rather it's distributed throughout the whole program. If, additionally, the state variables don't have the word "state" in their name, guessing that a certain code is a state machine in disguise is even harder.

Many programs we write are state machines. Think about a chess game for a moment. If we write a program to play chess against human beings, it's actually a state machine in some sense. It waits for the human to move - an idle state. Once the human moves, it goes into active state of "thinking" about a move to make. A game can have an "end" state such as a victory for one side or a draw. If we think of a GUI for a chess game, the state machine is even more obvious. There is a basic state, when it's a human's move. If a human clicks on some piece, we go into the "clicked" state. In this state, a click on an empty tile may produce a move by the piece. Note that if we click on an empty tile in the "basic" state

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.