1. Applications of finite automata

Finite automata

Finite automata

A finite automata is a tuple $(\mathcal{X},\mathcal{Q},q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $q_i\in \mathcal{Q}$ is the initial state
• $F\subseteq \mathcal{Q}$ is the set of accepting states
• $\delta :\mathcal{Q}\times \mathcal{X}\to \mathcal{Q}$ is the transition function

Link to original

Examples include:

• spell checkers
• search engine pattern matching
• compiler design
• specifying network protocols
• chip design
• speech recognition
• transforming text using markup languages like XML
• software optimisation