TOC-Regular language

Regular Language

Def: regular language

A language is regular if it is recognized by a DFA or an NFA.

To Prove a Language is regular, we need to construct a DFA or an NFA for the language.

Regular Operations

Def: Let and be languages.
  • Union :
  • Concatenation:

Star

Note: each is a string in the language A. And is the concatenation of , until .
Equivalently,

Def: Star operator

Let be a language. for is recursively define


Complement

Let be an arbitrary DFA. And we construct a new DFA . Prove that .

Note:

  • is the set difference.
  • is the set complement.

The goal is understood as set equality.
Thus, we need to prove , .

()
Assume .
Then .
Thus, DFA rejects .
In other words, DFA halts on a non-final state by consuming all symbols in .
By the construction of , is a final state of .
Thus, accepts , and .

()
Assume .
DFA accepts .
In other words, DFA halts on a final state by consuming all symbols in .
By the construction of , is a non-final state of .
Thus, rejects , so .
Thus, .

.

Let .

Closure

Theorem (Closure)

Regular language is closed under union, concatenation, star and complement.

if A and B are two regular languages, then , , and are also regular languages.

EaP8bA

Construct an NFA for .

$A\cup B$

ε

ε

(M_A)

(M_B)

ε

ε

q0

iA

fA

iB

fB

qf

Construct an NFA for .

$A \circ B$

ε

M_A

ε

M_B

ε

q0

iA

fA

iB

fB

qf

Construct an NFA for .

$A^{*}$

ε

M_A

ε

ε

ε

q0

iA

fA

qf

Regular Expression

Regular languages can be recursively constructed.
A regular expression describes the common pattern the strings in a regular language (machine independent).

Def: Regular expression (Recursive Definition)

is a regular expression over if is

  • for some ,
  • , or

  • , where and are regular expressions,
  • , where and are regular expressions, or
  • , where is a regular expression.

Languages Defined by Regular Expression

Def: Let be a regular expression. The language defined by is

  • ,
  • ,
  • , .

  • if , then
  • if , then
  • if , then

Example:

Suppose . Describe the language defined by the following regular expressions in English.

  • Match nothing

Equivalence of Regular Expression and Finite Automata

Theorem

Regular expressions are equivalent to finite automata.

The proof has two steps.

  1. The language defined by a regular expression can be recognized by a finite automaton.
  2. The conversion is also doable vice versa.

The conversion from a regular expression to an NFA is trivially ensured by the closure property .
So, we only need to convert NFA to regular expressions.

Conversion from NFA to Regular Expression

The Conversion requires generalized NFA, which is a special type of NFA.

Only one start state and one final state.
The start state is different from the final state.
The transition function is

Suppose

  • It means transition from to requires .
  • If the GNFA has only 2 states and , then the label on the transition is the regular expression for the language.
  • Thus, the conversion recursively merges states and transitions of the generalized NFA.

Algorithm Convert NFAε_\varepsilon to 2-state gNFA

Input: An NFA N=(Q,Σ,δ,q0,F)N = (Q, \Sigma, \delta, q_0, F)

Output: A regular expression which defines L(N)L(N)

N′←NN' \gets N // convert the domain and codomain of the transition function

Q′←Q′∪{q0′,qf′}Q' \gets Q' \cup \{q_0', q_f'\}

δ′(q0′,q0)=ε\delta'(q_0', q_0) = \varepsilon

for all q∈Fq \in F do

δ′(q,qf′)=ε\delta'(q, q_f') = \varepsilon

end for

for all state qq in Q′Q' except q0′q_0' and qf′q_f' do

Q′←Q′∖{q}Q' \gets Q' \setminus \{q\}

for all state qiq_i in Q′Q' except qf′q_f' do

for all state qjq_j in Q′Q' except q0′q_0' do

Suppose δ′(qi,q)=R1\delta'(q_i, q) = R_1, δ′(q,q)=R2\delta'(q, q) = R_2, δ′(q,qj)=R3\delta'(q, q_j) = R_3, and δ′(qi,qj)=R4\delta'(q_i, q_j) = R_4

δ′(qi,qj)=((R1)(R2)∗R3)∪(R4)\delta'(q_i, q_j) = ((R_1)(R_2)^* R_3) \cup (R_4)

end for

end for

end for

return δ′(q0′,qf′)\delta'(q_0', q_f')

Table Of Contents
TOC-Regular language
Regular Language
Regular Operations
Star
Complement
Closure
Construct an NFA for .
Construct an NFA for .
Construct an NFA for .
Regular Expression
Languages Defined by Regular Expression
Equivalence of Regular Expression and Finite Automata
Conversion from NFA to Regular Expression