Exercise 1.2.1: Describe the strings that are accepted by the deterministic finite automaton represented in the following transition diagram.
Let’s just follow the arrows. We start and we need a letter to get into the acceptance state. In this state we can have either a letter or a digit. Therefore the strings start with a letter and then are followed by a letters of digits. Examples: r2d2, Hello, Mr234S
Exercise 1.2.3: Identify another deterministic finite automaton in everyday life and draw its transition diagram.
The book listed the example of a vending machine and a telephone call. Both receive strings and jump between states. One other common example which I choose are traffic lights.
Let’s make it super easy, i.e. a traffic light which just switches between red, yellow, green for cars and red and green for pedestrians. Also there’s no option for the pedestrians to request green light.
The signal in our case is a timer. I also assume for simplicity that each transition has the same delay.
I represent the state as a tuple of (light cars, light pedestrians).
The starting state is (green, red).
(green,red) -> (yellow, red) -> (red, red) -> (red, green) -> (red, red) -> to the start
It’s a bit more boring then the other examples because it just cycles through its states but you can think about the diagram using a request button for pedestrians.