Question

Explain why Thompson's Construction Algorithm is considered to be a proof by induction. Hint: consider what the inductive steps and base cases are. What does Thompson's Construction Algorithm prove

Answer 1

We assume that the NFA for the expression S is theorem by using the expressions given below.

Cases as

• NFA for empty-expression is ε

• NFA for symbol is a
• NFA for union expression is a|b
• NFA for concatenation expression is ab
• NFA for Kleene star expression is a*

Thompson's Construction Algorithm proves that any expression can be expressions in the NFA's.