SD04 - Finite State Automata

Question 1

What is the difference between a finite-state machine and a finite-state automaton?

Answer 1

An FSA doesn’t produce output. It instead accepts or rejects an input string as valid

Question 2

What is the 5-tuple of a finite-state automaton?

Answer 2

F = (S, σ, A, I, f)

Question 3

Why is it impractical to create a FSA to recognise ‘well bracketed’ expressions?
e.g. Accept (1+2), Reject (1+2

Answer 3

The number of brackets is infinite and therefore an infinite number of states is needed to keep track of them

Question 4

What is a non-deterministic finite-state automaton?

Answer 4

An FSA where there can be several options for each input symbol.
An nFSA accepts a string if there’s any path
through it that would have accepted it.

Question 5

How can two FSAs (F1 and F2) be added together?

Answer 5

Link the accepting states of F1 to the initial state of F2 with silent moves