Formal Language
Regular language⚓︎
Finite automata⚓︎
The definition of finite automata⚓︎
- \(Q\) : state
- \(\sum\) : alphabet(like action)
- \(\delta\) : transition function \((Q \times \sum \rightarrow Q)\)
- \(q_{0}\) \(\in Q\) : start state
- \(F \subseteq Q\) : the set of accept/final state
Accept the string⚓︎
Accept the string \(w=w_{0}...w_{n}\) when 1. \(r_{0}\) = \(q_{0}\) 2. \(\delta(r_{i},w_{i+1}) = r_{i+1}\) 3. \(r_{n} \subseteq F\)
Accept and recognize⚓︎
\(L(M) =A \rightarrow\)
\(M\) recoginze \(A\) languages or
\(M\) accept the set of all string \(A\)
A language is called a regular language if some finite automaton recognizes it.
The regular operator⚓︎
-
Union :
If \(\sum_{1} and \sum_{2}\) are same.
Estabalish a machine that simultaneously track 2 machine, E.g. Cartisian product. -
Concatenation
- Star