date: 2024-10-26
title: 04-TOC-RL
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- Regular-Expression
publish: True
TOC-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.
Note: each
Equivalently,
Let
Let
Note:
The goal
Thus, we need to prove
(
Assume
Then
Thus, DFA
In other words, DFA
By the construction of
Thus,
(
Assume
DFA
In other words, DFA
By the construction of
Thus,
Thus,
Let
Regular language is closed under union, concatenation, star and complement.
if A and B are two regular languages, then
Regular languages can be recursively constructed.
A regular expression describes the common pattern the strings in a regular language (machine independent).
Example:
Suppose
Regular expressions are equivalent to finite automata.
The proof has two steps.
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.
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
Algorithm Convert NFAε to 2-state gNFA
Input: An NFA N=(Q,Σ,δ,q0,F)
Output: A regular expression which defines L(N)
N′←N // convert the domain and codomain of the transition function
Q′←Q′∪{q0′,qf′}
δ′(q0′,q0)=ε
for all q∈F do
δ′(q,qf′)=ε
end for
for all state q in Q′ except q0′ and qf′ do
Q′←Q′∖{q}
for all state qi in Q′ except qf′ do
for all state qj in Q′ except q0′ do
Suppose δ′(qi,q)=R1, δ′(q,q)=R2, δ′(q,qj)=R3, and δ′(qi,qj)=R4
δ′(qi,qj)=((R1)(R2)∗R3)∪(R4)
end for
end for
end for
return δ′(q0′,qf′)