Introduction, Finite Automata, Regular Expression

Video

Finite automaton

Formal definition

5-tuple $(Q,\Sigma ,\delta ,q_0,F)$

1. $Q$ is a finite set called the states,
2. $\Sigma$ is a finite set called the alphabet,
3. $\delta :Q\times \Sigma \to Q$ is the transition function,
4. $q_0\in Q$ is the start state, and
5. $F\subseteq Q$ is the set of accept states.

Strings and language

• A string is a finite sequence of symbols in Σ

• A language is a set of strings (finte or infinite)

• The empty string $ϵ$ is the string of length 0

• The empty language $\varnothing$ is the set with no strings

• $L(M)$ = {w| M accepts w}

• L(M) is the language of M

• M recognizes L(M)

Regular language

DefA language is regular if some finite automaton recognizes it.

Regular Expressions

Regular operations. Let A, B be languages

• Union: $A\bigcup B$
• Concatenation: $A\circ B$
• Star: $A^{\ast }$

Example. Let A = {good, bad} and Let B = {boy, girl}.

• $A\bigcup B$ = {good, bad, boy, girl}
• $A\circ B$ = $AB$ = {goodboy, goodgirl, badboy, badgirl}
• $A^{\ast }$ = {ε, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, … }

Regular expressions

• Build from Σ, Members are $\Sigma ,\varnothing ,ϵ$ [Atomic]
• By using $\bigcup ,\circ ,\ast$ [Composite]

Examples

• $(0\bigcup 1)\ast$ = ${\Sigma }^{\ast }$
• ${\Sigma }^{\ast }1$ = a
• ${\Sigma }^{\ast }11{\Sigma }^{\ast }$ = a

Closure properties for Regular Expressions

If $A_1,A_2$ are regular languages, so is $A_1\bigcup A_2$ (closure under $\bigcup$)

The class of regular languages is closed under the union operations.