Regular Expressions and FSA
In class exercise
Peer suggested tool:
mapper: .http://www.xmind.net/

1-a Make a map for a maze.  (At least 3*3 with more than one path possible.)
From each spot in the maze you can go N S E W . Label entrance and exit.
Average path thru the maze might be around 7 steps.

1-b Give TWO paths through the maze that go from the entrance to the exit.

1-c Using these paths, give a REGULAR EXPRESSION of how to get through the maze.
Does your REGULAR EXPRESSION describe all possible paths through the maze?

1-d Describe how you would produce a Finite State Automata that completely described the maze, so that it would recognize all paths through the maze.

2a- If you have not already done so, do an FSA diagram/map for your ‘inform7 story’.
(If you have not finished your inform7 project, do a map for your preliminary inform7 and then hand in a map with your final inform7 story.

2b- (Do you have any loops?  What does a loop mean?)

2c-Can your inform7 game be completely done with a finite state automata?
Why or why not?

BONUS QUESTION:
Given binary inputs: (you don’t need all of these)
 Wall on right
 Wall in front
 Wall on left
 Wall behind
 At goal
And possible actions: (you don’t need all of these)
Turn right
Turn left
Turn around
Move forward

Attempt to design a FSA to escape from a maze.
The best solution will be made available to the Robotics club. :)

						Regular Expressions and CFG
Given the following grammar:
S -> F L
F -> C V T
C -> b | h | f | v
V ->a | ai | ei | i
T -> th | ph
L-> U | U V | UUV
U -> CV
Can you write a regular expression to recognize this language?
Why or why not? 
Can you describe the language in English?
Would this grammar work for generating names in a game?

Given the following grammar:
S-> aBa |B | NULL
B-> bSb | S | NULL
Can you write a regular expression to recognize this language?
Why or why not? 
Can you describe the language in English?