代写 R C algorithm Java parallel COMP2022: Formal Languages and Logic

COMP2022: Formal Languages and Logic
2018, Semester 2, Week 5
Joseph Godbehere 30th August, 2018

COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING
This material has been reproduced and communicated to you by or on behalf of the University of Sydney pursuant to part VB of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any further copying or communication of this material by you may be subject of copyright protect under the Act.
Do not remove this notice.

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA) ▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties ▶ Regular Expressions (introduction)
3/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Non deterministic Finite Automata (NFA)
DFA
▶ has exactly one transition per input from each state ▶ no choice in the computation =⇒ deterministic
NFA
▶ can have any number of transitions per input from each state
▶ so some steps of the computation might be non-deterministic ▶ can also have ε-transitions
▶ i.e. transitions which the automaton can follow without scanning any input
4/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Non-determinism
▶ As we scan through a string, the NFA can be in many states at the same time
▶ Transitions from a state given an input symbol is to a set of states (0, 1, 2 or more states)
▶ The string is accepted if at least one sequence of states leads to a final state
▶ i.e. if we are in at least one accept state, after reading all the input
▶ Parallel computation
5/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
NFA accepting strings over {0, 1} containing substring “000” 0,1 0,1
q0 0 q1 0 q2 0 q3 The corresponding DFA would be
1
q0 0 q1
1
1
0 q2
0,1
0 q3
6/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA with ε-Transitions
▶ ε-transitions do not consume any input ▶ Remember that ε is the empty string
7/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ From A, with a 0: ▶ FromA,witha1: ▶ From B, with ε: ▶ From E, with ε:
B
1
D
0
A
1
ε
ε
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ FromA,witha0: B ▶ FromA,witha1:
▶ From B, with ε:
▶ From E, with ε:
B
1
D
0
A
1
ε
ε
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ FromA,witha0: B ▶ FromA,witha1: E ▶ From B, with ε:
▶ From E, with ε:
B
1
D
0
A
1
ε
ε
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ FromA,witha0: B ▶ FromA,witha1: E ▶ FromB,withε: D ▶ From E, with ε:
B
1
D
0
A
1
ε
ε
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ FromA,witha0: B
▶ FromA,witha1: E
▶ FromB,withε: D
▶ FromE,withε: BandC
B
1
D
0
A
1
ε
ε
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
B
1
ε
C
1
D
▶ FromA,witha0: B
▶ FromA,witha1: E
▶ FromB,withε: D
▶ FromE,withε: BandC
0
A
1
ε
ε
0 E0F
So from A with 0, we can potentially also reach D without needing to scan more input.
(Epsilon closure (later in the lecture))
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
ε
C 1
0 E0F
▶ FromA,witha0: B
▶ FromA,witha1: E
▶ FromB,withε: D
▶ FromE,withε: BandC
01ε A{E}{B} ∅
B ∅ {C} {D} C ∅ {D} ∅
B
1
D
0
A
1
εε
So from A with 0, we can potentially also reach D without needing to scan more input.
(Epsilon closure (later in the lecture))
D
E {F} ∅ {B,C} F {D} ∅ ∅
∅∅∅
8/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Formal definition of NFA
Definition: A non-deterministic finite automaton is a 5-tuple ▶ (Q,Σ,δ,q0,F) where:
▶ Q is a finite set called the states,
▶ Σ is a finite set called the alphabet,
▶ δ : Q × Σε → P(Q) is the transition function*, ▶ q0 is the start state, and
▶ F ⊆ Q is the set of accept states.
*Recall:
▶ ifA={a,b,c}then
P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
▶ abε=aεb=εab=ab
▶ Σε = Σ ∪ {ε}
9/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Transition function for NFA
δ : Q × Σε → P(Q)
▶ δ(q,a) is a set of states which is the union of all the states which can be reached from q on a.
▶ This could be the empty set ∅
▶ Note: when following epsilon transitions, you can also remain inthesamestate(asif q∈δ(q,ε)forallq∈Q)
10/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
0,1 0,1
q 0 q 0,ε q 1 q 1234
▶ Q = {q1,q2,q3,q4}
▶Σ=?
▶ The start state is q1
▶ The set of accept states is {q4}
Some strings where N reaches the accept state: 01, 0000001
δ:Q×Σε →P(Q)isgivenby:
0
1
ε
q1
{q1, q2}
{q1 }
∅
q2
{q3 }
∅
{q3 }
q3
∅
{q4 }
∅
q4
{q4 }
{q4 }
∅
11/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
0,1 0,1
q 0 q 0,ε q 1 q 1234
▶ Q = {q1,q2,q3,q4}
▶Σ= {0,1}
▶ The start state is q1
▶ The set of accept states is {q4}
Some strings where N reaches the accept state: 01, 0000001
δ:Q×Σε →P(Q)isgivenby:
0
1
ε
q1
{q1, q2}
{q1 }
∅
q2
{q3 }
∅
{q3 }
q3
∅
{q4 }
∅
q4
{q4 }
{q4 }
∅
11/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA computation : Parallelism
0,1 0,1
q 0 q 0,ε q 1 q 1234
Several choices that exist can be seen as parallel computation or as a tree of possibilities
Read 1 – – – – Read 0 – – – – Read 0 – – – – Read 1 – – – –
q1
q1 q2
q1
q1
q2 q3
q3 q3
q1
q4q4
12/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Language of an NFA
▶ A string w is accepted by an NFA if at least one sequence of transitions starting from q0 on input w leads to an accept state
▶ i.e. if we are in at least one accept state, after reading all the input
▶ The language recognised by an NFA (i.e. the set of strings it accepts) is called regular
13/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (1)
L1: Strings over {a, b, c} ending with an a
a,b,c
q1 a q2
14/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (2)
L2: Strings over {a, b, c} composed of at least one repetition of the substring ab
q1 a q2 b q3
ε
15/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (3)
L3: Strings over {0,1} with a 1 in the third last position
0,1
q 1 q 0,1 q 0,1 q 1234
16/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Equivalence of NFAs and DFAs
▶ DFA: exactly one transition per input from each state
▶ NFA: zero, one or several possible transitions, ε-transitions ▶ =⇒ any DFA is a NFA (NFA more general)
But are there languages that are recognised by some NFA but not by a DFA?
No. If a language is recognised by a NFA then we can always devise a DFA which recognises it.
Theorem: Every NFA has an equivalent DFA
18/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular languages and finite automata
Theorem (Kleene 56):
The class of regular languages is exactly the same as the class of languages accepted by DFAs
Theorem (Rabin & Scott 59):
The class of regular languages is exactly the same as the class of languages accepted by NFAs
=⇒ Any regular language must be accepted by at least one DFA and at least one NFA
Can we transform NFAs into DFAs?
19/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Transforming a NFA into a DFA: intro
Key idea: Read the NFA as if it was a DFA and keep in memory the possible set of states it could be in for each given input (i.e. similar to the levels of the decision tree example.)
Each state of the new DFA is a subset of the NFA states (subset construction)
When we transition from a state X, with a given input symbol i, we must also consider all the ways in which we could follow epsilon transitions before and after reading i
▶ i.e. We transition to the set of states reachable via paths using any number of ε transitions before and/or after i
20/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q, denoted E(q), is the set of all states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E(q)
▶ If p ∈ E(q) and there is an ε-transition from p to r, then r ∈ E(q)
21/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure for sets
The Epsilon-closure of a set of states S, denoted E(S), is the union of the Epsilon-closure of each state.
E(S ∪T) = E(S)∪E(T)
22/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
a
ε
E({q1})= E({q2})= E({q3})= E({q4})= E({q5})=
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
q1
q2 ∅
{q2 }
q3
q4
q5 ∅
{q2 } {q3, q5}
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
a
ε
E({q1})= {q1, q2} E({q2})= E({q3})= E({q4})= E({q5})=
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
q1
q2 ∅
{q2 }
q3
q4
q5 ∅
{q2 } {q3, q5}
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
a
ε
E({q1})= {q1, q2} E({q2})= {q2 } E({q3})= E({q4})= E({q5})=
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
q1
q2 ∅
{q2 }
q3
q4
q5 ∅
{q2 } {q3, q5}
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
q1
q2
q3
q4
q5 ∅
a
ε
E({q1})= {q1, q2} E({q2})= {q2 } E({q3})= {q2, q3} E({q4})= E({q5})=
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
{q2 } ∅ {q2 } {q3, q5}
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
q1
q2
q3
q4
q5 ∅
a
ε
E({q1})= {q1, q2} E({q2})= {q2 } E({q3})= {q2, q3} E({q4})= {q2, q3, q4, q5} E({q5})=
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
{q2 } ∅ {q2 } {q3, q5}
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
q1
q2
q3
q4 {q3, q5} q5 ∅
a
ε
E({q1}) = {q1,q2} E({q2}) = {q2}
E({q3}) = {q2,q3}
E ({q4}) = {q2, q3, q4, q5} E({q5}) = {q5}
E({q1,q3,q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
{q2 } ∅ {q2 }
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
q1
q2
q3
q4 {q3, q5} q5 ∅
a
ε
E({q1}) = {q1,q2} E({q2}) = {q2}
E({q3}) = {q2,q3}
E ({q4}) = {q2, q3, q4, q5} E({q5}) = {q5}
E ({q1, q3, q5})
= E({q1}) ∪ E({q3}) ∪ E({q5}) =
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
{q2 } ∅ {q2 }
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
εε
q ε q a q b q a,ε q
12345
q1
q2
q3
q4 {q3, q5} q5 ∅
a
ε
E({q1}) = {q1,q2} E({q2}) = {q2}
E({q3}) = {q2,q3}
E ({q4}) = {q2, q3, q4, q5} E({q5}) = {q5}
E ({q1, q3, q5})
= E({q1}) ∪ E({q3}) ∪ E({q5}) = {q1, q2, q3, q5}
a
b
∅
∅
{q3, q4}
∅
∅
{q4 }
{q5 }
∅
∅
∅
{q2 } ∅ {q2 }
23/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA to DFA algorithm
We want to convert a NFA N = (Q,Σ,δ,q0,F) into an equivalent DFA M = (Q′,Σ,δ′,q0′,F′) which recognises L(N)
Algorithm
1. DFA start state is E(q), where q is the NFA start state
2. IfR⊆P(Q)isaDFAstateanda∈Σthenconstructthe following DFA state as a DFA table entry in either 2 ways:
▶ δ′(R,a) = E(∪r∈Rδ(r,a)) closure of union ▶ δ′(R,a) = ∪r∈RE(δ(r,a)) union of closures
3. A DFA state is accepting if any of its elements are an NFA accept state.
25/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
εε
q ε q a q b q a,ε q
12345
Transition table:
a
a
b
Resulting DFA:
26/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
εε
q ε q a q b q a,ε q
12345
Transition table:
a
a
b
E(start) =
Resulting DFA:
26/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
εε
q ε q a q b q a,ε q
12345
Transition table:
a
a
b
E(start) = {q1,q2}
Resulting DFA:
26/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
εε
q ε q a q b q a,ε q
12345
Transition table:
a
a
b
E(start) = {q1,q2}
{q2, q3, q4, q5}
Resulting DFA:
26/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
εε
q ε q a q b q a,ε q
12345
Transition table:
A B C
Resulting DFA:
a
a
b
E(start) = {q1,q2} {q2, q3, q4, q5}
∅
{q2, q3, q4, q5} {q2, q3, q4, q5} ∅
∅
{q2, q3, q4, q5} ∅
b
A a B a,b C a,b
26/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) =
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2}
{q1, q2, q3}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3}
{q1, q2, q3} {q1, q2, q3}
{q1,q2} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q3} {q1, q2, q3}
{q1,q2} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 a q3 b q4 Transition table:
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4} {q1, q2, q4} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
a,b a,b
q1 ε q2 Transition table:
A B C D
a q3
b q4
a
b
E(start) = {q1,q2} {q1, q2, q3} {q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q3, q4} {q1, q2, q3, q4}
{q1,q2} {q1, q2, q4} {q1, q2, q4} {q1, q2, q4}
27/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Minimisation of DFA (idea)
Every DFA has a unique equivalent minimal DFA
Definition: Two states s and t are equivalent if: for any string, the path from s leads to an accepting state if and only if the path from t does.
To reduce an automaton, find all non-equivalent states:
1. If s is accepting and t non accepting, then they are not equivalent
2. If, with input x, there is a transition from s to s′ and from t to to t′ and we know that s′ and t′ are not equivalent, then s and t are not equivalent
Then merge equivalent states.
29/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Minimisation of DFA: Table-filling Algorithm
1. Examine all pairs of states and find all pairs s,t that are NOT equivalent, ie satisfying either of:
1.1 s is accepting and t is not or vice versa
1.2 withthesameinputx,s goestoastates′ andt toastatet′
and you have already proven that s′ and t′ are NOT equivalent 2. When no further non-equivalence can be proven, then the
remaining pairs can be merged respectively into one state.
Theorems:
1. If two states are not distinguished by the table-filling algorithm, then the states are equivalent
2. The equivalence of states is transitive
30/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
0
1 A1B1C
00 00
11 DE
31/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
–
–
–
–
C
–
–
–
D
–
–
E
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
x
–
–
–
–
C
x
–
–
–
D
x
–
–
E
x
x
x
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
2. Look at each remaining pair.
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
x
–
–
–
–
C
x
–
–
–
D
x
–
–
E
x
x
x
x
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A,0)=Aandδ(E,0)=C,butA̸≡C,thereforeA̸≡E
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
x
–
–
–
–
C
x
x
–
–
–
D
x
–
–
E
x
x
x
x
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A,0)=Aandδ(E,0)=C,butA̸≡C,thereforeA̸≡E ▶ δ(B,0)=Dandδ(C,0)=E,butD̸≡E,thereforeB̸≡C
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
x
–
–
–
–
C
x
x
–
–
–
D
x
–
–
E
x
x
x
x
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A,0)=Aandδ(E,0)=C,butA̸≡C,thereforeA̸≡E
▶ δ(B,0)=Dandδ(C,0)=E,butD̸≡E,thereforeB̸≡C ▶ Wecan’tfindareasontoclaimB̸≡Dyet
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A
–
–
–
–
–
B
x
–
–
–
–
C
x
x
–
–
–
D
x
x
–
–
E
x
x
x
x
–
A
B
C
D
E
1. Cross out all the pairs of accept/non-accept states. A, E are non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A,0)=Aandδ(E,0)=C,butA̸≡C,thereforeA̸≡E
▶ δ(B,0)=Dandδ(C,0)=E,butD̸≡E,thereforeB̸≡C ▶ Wecan’tfindareasontoclaimB̸≡Dyet
▶ δ(C,0)=Eandδ(D,0)=B,andE̸≡B,thereforeC̸≡D
32/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Merging equivalent states
Theorem: If two states are not distinguished by the table-filling algorithm, then that pair of states are equivalent.
We can merge together equivalent states. The minimal DFA for the example becomes:
00
1
A 1 BD 1 C
00 E
1
33/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Resulting DFA
▶ is minimal ▶ is unique
34/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Revision
Definition:
A language is regular if and only if there exists a finite automaton which recognises it.
Minimal examples:
▶ ∅ is a regular language
▶ {ε} is a regular language
▶ For all a ∈ Σ, the set {a} is a regular language
Think about how to make a DFA for each of these languages
36/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Closure properties of Regular languages
Let L1 and L2 be regular languages.
The regular operations are defined as follows:
▶ Union: L1 ∪ L2 = {w|w ∈ L1 or w ∈ L2}
▶ Concatenation: L1L2 = {w1w2|w1 ∈ L1 and w2 ∈ L2}
▶ Star: L∗ = {w1w2…wk|k ≥ 0 and wi ∈ L for i = 1,…,k}
Theorems
▶ The union of two regular languages is regular
▶ The concatenation of two regular languages is regular ▶ The star closure of a regular language is regular
37/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union of two regular languages
If L1 and L2 are regular, then finite automata M1 and M2 exist which recognise them. we can construct an automaton M which recognises L1 ∪L2 = {w|w ∈ L1 or w ∈ L2}:
q1 ε
q0
ε
M1 M2
q2
38/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union of two regular languages
Let M1 = (Q1,Σ,δ1,q1,F1), M2 = (Q2,Σ,δ2,q2,F2) Let M = (Q,Σ,δ,q0,F) where:
▶ Q = {q0} ∪ Q1 ∪ Q2
▶ q0 is the new start state
▶ Transition function δ defined for any q ∈ Q and any a ∈ Σε 
δ1(q,a)
δ2(q,a) δ(q,a) = {q1,q2}
∅
▶ Accepting set F = F1 ∪ F2
M accepts if and only if M1 or M2 does i.e.L(M)={w|w∈L1 orw∈L2}=L1∪L2
if q ∈ Q1
if q ∈ Q2
if q = q0 and a = ε ifq=q0 anda̸=ε
39/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Concatenation of two regular languages
If L1 and L2 are regular, then finite automata M1 and M2 exist which recognise them.
we can construct an automaton M which recognises L1L2 = {w1w2|w1 ∈ L1 and w2 ∈ L2}:
M1 ∈F M2 1ε
q1 ∈ F1 ε q2
Note that the accept states of M1 are not accept states in M
40/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Concatenation of two regular languages
Let M1 = (Q1,Σ,δ1,q1,F1), M2 = (Q2,Σ,δ2,q2,F2) Let M = (Q,Σ,δ,q0,F) where:
▶ Q = Q1 ∪ Q2
▶ q1 is start state (same as M1)
▶ Transition function δ defined for any q ∈ Q and any a ∈ Σε 
δ1(q,a)
δ1(q,a) δ(q,a) = δ1(q,a)∪{q2}
δ2(q,a)
▶ Accepting set F = F2 (same as M2) L(M) = {w1w2|w1 ∈ L1 and w2 ∈ L2} = L1L2
if q ∈ Q1 and q ̸∈ F1 ifq∈F1 anda̸=ε if q ∈ F1 and a = ε if q ∈ Q2
41/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Star closure of a regular language
If L is regular, then a finite automaton M1 exists which recognises it.
we can construct an automaton M which recognises L∗ = {w1w2…wk|k ≥ 0 and wi ∈ L for i = 1,…,k}:
ε
q0 ε q1
e.g. if L = {a, b} then this automaton recognises {ε,a,b,aa,ab,bb,aaa,…} = L∗
ε
M1
42/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Star closure of a regular language
Let M1 = (Q1,Σ,δ1,q1,F1)
Let M = (Q,Σ,δ,q0,F) where:
▶ Q = Q1 ∪ {q0}
▶ q0 is the new start state
▶ Transition function δ defined for any q ∈ Q and any a ∈ Σε
 δ1(q,a)
δ1(q,a) δ(q,a) = δ1(q,a)∪{q1}
{q1} ∅
▶ Accepting set F = F1 ∪ {q0} L(M)={w1w2…wk|k≥0andwi ∈Lfori=1,…,k}=L∗
if q ∈ Q1 and q ̸∈ F1 ifq∈F1 anda̸=ε if q ∈ F1 and a = ε ifq=q0 anda=ε ifq=q0 anda̸=ε
43/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
Construct an NFA recognising the set of strings containing the pattern aaab or the strings composed of 0 or more sequences of ab
44/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example from construction to minimal DFA
Let Σ = {0,1}
Let L1 be the language of strings which do not contain consecutive 0’s
Let L2 be the language of strings ending with 0
45/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Complement of a regular language
The complement of a regular language is regular The complement of a language L is {x |x ̸∈ L}
Example:
Let L1 = {x|x contains an odd number of a’s}
Then the complement of L1 is L2 = {x|x ̸∈ L1} = {x|x contains an even number of a’s}
You will explore how to construct a suitable automata in this week’s tutorial
46/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Intersection of a regular language
If L1 and L2 are regular, then L1 ∩ L2 is regular.
We can use the cross product technique to build the DFA
Example:
L1 = {x|x ∈ {a,b}∗ and x contains an odd number of a’s} L2 = {x|x ∈ {a,b}∗ and x contains an odd number of b’s}
M1 M2 AbC
b
A,C b A,D aa aa
B,C b B,D
b
a bb
a
aa BbD
47/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Cross-product of DFAs
Let M1 = (Q1,Σ,δ1,q1,F1), M2 = (Q2,Σ,δ2,q2,F2) be two DFA Let M = (Q,Σ,δ1,q0,F) where:
▶ Q = Q1 ×Q2 (i.e. all ordered pairs (u,v) such that u ∈ Q1 and v ∈ Q2)
▶ The start state (q1,q2) is the pair of start states from Q1 and Q2
▶ The transition function δ is defined as: δ((u,v),x) = (δ1(u,x),δ2(v,x))
▶ Accepting set F = {(u,v)|u ∈ F1 and v ∈ F2} Note that M is also deterministic
48/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example Cross-product for Intersection
Example:
L1 = {x|x ∈ {a,b}∗ and x contains an odd number of a’s} L2 = {x|x ∈ {a,b}∗ and x contains an odd number of b’s}
M1 M2 AbC
b
A,C b A,D aa aa
B,C b B,D
b
a bb
a
aa BbD
49/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Cross-product can be used for Union
Example:
L1 = {x|x ∈ {a,b}∗ and x contains an odd number of a’s} L2 = {x|x ∈ {a,b}∗ and x contains an odd number of b’s}
M1 M2 AbC
b
A,C b A,D aa aa
B,C b B,D
b
a bb
a
aa BbD
50/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions
In arithmetic we use operations to build up expressions, describing numbers such as
(5+3)×4 (value is 32) 4/2 − 1 (value is 1)
With regular languages, we use regular operations to build up expressions describing languages such as
(0 | 1)0⋆ (strings starting with 0 or 1, then any number of 0’s) (ab)⋆a (any number of ab’s, followed by a)
52/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions vs Finite Automata
▶ RegEx: algebraic description of the strings in a language
▶ FA: a machine-like description
▶ RegEx serve as the input language for many systems which process strings
▶ Search commands ▶ UNIX grep
▶ Web browsers
▶ Text editors
▶ Text formatting systems ▶ …
▶ Lexical-analyser generators (Lex, Flex, etc.)
▶ Like FA, RegEx define exactly the class of regular languages
53/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Definition of a Regular Expression (RegEx)
▶ Basic expressions and the language they describe
▶ If a is any symbol of the input alphabet, then a is a RegEx
and its language L(a) = {a}
▶ εisaRegExandL(ε)={ε}
▶ ∅isaRegExandL(∅)=∅
▶ Operators on RegEx. If R and S are RegEx, then
▶ Union: R | S (sometimes denoted R + S ) is a RegEx
▶ Concatenation: RS (sometimes denoted R ◦ S ) is a RegEx ▶ Star Closure: R⋆ is a RegEx
54/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Language of a Regular Expression
Let x,y be symbols from the input alphabet
L(x) = {x} L(ε) = {ε} L(∅) = {∅}
L(x |y)={x,y}
L(x⋆) = {ε,x,xx,xxx,…} L(xy) = {xy}
55/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S Definition: L(R | S) = L(R) ∪ L(S)
56/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S) = L(R) ∪ L(S) L(a | b) =
56/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S Definition: L(R | S) = L(R) ∪ L(S)
L(a | b) = L(a)∪L(b) = {a}∪{b} = {a,b}
L(b | a) = L(b)∪L(a) = {b}∪{a} = {a,b} = L(a | b) L((a |b)|c)=L(a |b)∪L(c)
= {a, b} ∪ {c} =
56/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS Definition: L(RS) = {rs | r ∈ L(R) and s ∈ L(S)}
57/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS) = {rs | r ∈ L(R) and s ∈ L(S)} L(ab) =
57/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS Definition: L(RS) = {rs | r ∈ L(R) and s ∈ L(S)}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba} L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}} =
57/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS Definition: L(RS) = {rs | r ∈ L(R) and s ∈ L(S)}
L(ab) =
L(ba) = L((ab)c) =
{rs | r ∈ L(a) and s ∈ L(b)} = {ab} {rs | r ∈ L(b) and s ∈ L(a)} = {ba} {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) =
57/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS Definition: L(RS) = {rs | r ∈ L(R) and s ∈ L(S)}
L(ab) =
L(ba) = L((ab)c) =
{rs | r ∈ L(a) and s ∈ L(b)} = {ab} {rs | r ∈ L(b) and s ∈ L(a)} = {ba} {rs | r ∈ L(ab) and s ∈ L(c)}
L(a(bc)) = =
{rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
57/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) =
L((ab) | c) =
58/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)} =
L((ab) | c) =
58/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
=
L((ab) | c) =
58/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a,b} and s ∈ {c}} = {ac,bc}
L((ab) | c) = L(ab) ∪ L(c) =
58/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆ R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …} L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) = {ε}∪L(∅)∪… = {ε} L(a | bc⋆) =
59/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = L((01)⋆) = L(∅⋆) = L(a | bc⋆) = L(a | (bc)⋆) = L((a | b)c⋆) =
{ε, 0, 00, 000, …}
{ε, 01, 0101, 010101, …} {ε}∪L(∅)∪… = {ε} {a, b, bc, bcc, bccc, …} {a, ε, bc, bcbc, bcbcbc, …}
59/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R, S , T be regular expressions
▶ Union properties:
▶ R|S=S|R(commutative)
▶ R|∅=∅|R=R
▶ R|R=R
▶ (R|S)|T=R|(S|T)(associative)
▶ Concatenation properties:
▶ Union and concatenation are distributive when combined:
60/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R, S , T be regular expressions
▶ Union properties:
▶ R|S=S|R(commutative)
▶ R|∅=∅|R=R
▶ R|R=R
▶ (R|S)|T=R|(S|T)(associative)
▶ Concatenation properties: ▶ R∅=∅R=∅
▶ Rε=εR=R
▶ (RS )T = R(ST ) (associative)
▶ Union and concatenation are distributive when combined:
60/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R, S , T be regular expressions
▶ Union properties:
▶ R|S=S|R(commutative)
▶ R|∅=∅|R=R
▶ R|R=R
▶ (R|S)|T=R|(S|T)(associative)
▶ Concatenation properties: ▶ R∅=∅R=∅
▶ Rε=εR=R
▶ (RS )T = R(ST ) (associative)
▶ Union and concatenation are distributive when combined:
▶ R(S|T)=RS|RT ▶ (S|T)R=SR|TR
60/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R, S , T be regular expressions
▶ Star Closure properties: ▶ ∅⋆ = ε⋆ = ε
61/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R, S , T be regular expressions
▶ Star Closure properties: ▶ ∅⋆ = ε⋆ = ε
▶ R⋆ =R⋆R⋆ =(R⋆)⋆ =R|R⋆
▶ R⋆ =ε|R⋆ =(ε|R)⋆ =(ε|R)R⋆ =ε|RR⋆
▶ RR⋆ = R⋆R
▶ (R | S)⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S)⋆R⋆ = R⋆(SR⋆)⋆
61/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c ▶ Strings over {0, 1} which end with 01
▶ Traffic lights?
▶ Identifiers for Java programs?
62/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c (a | b | c)⋆
▶ Strings over {0, 1} which end with 01 ▶ Traffic lights?
▶ Identifiers for Java programs?
62/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c (a | b | c)⋆
▶ Strings over {0, 1} which end with 01 (0 | 1)⋆01
▶ Traffic lights?
▶ Identifiers for Java programs?
62/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c (a | b | c)⋆
▶ Strings over {0, 1} which end with 01 (0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
62/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c (a | b | c)⋆
▶ Strings over {0, 1} which end with 01 (0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs? (letter | $ | _)(letter | digit | $ | _)⋆
62/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
▶ ((a | b)(a | b))⋆ represents ▶ ab⋆a | ba⋆b | a | b represents
▶ a⋆∅ represents
63/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a,b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s starting and ending with a, or a single a or b
▶ a⋆∅ represents
63/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Equivalence of RegEx and FA
Theorem:
A language is regular if and only if a regular expression describes it.
Proof:
Show the equivalence of RegEx and FA (RegEx ⇔ FA)
1. RegEx ⇒ FA:
Show that for each RegEx, there exists an NFA which recognises the same language
2. FA ⇒ RegEx:
Show that for each NFA, there exists a RegEx which recognises the same language
64/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Application: pattern matching
▶ Provides a technique for finding occurrences of patterns in text (e.g. web/document searching)
▶ Some of the best known algorithms are based on Finite Automata!
▶ Constructing a NFA to recognise the strings containing the pattern is trivial.
▶ Then we convert the NFA to DFA, then minimal DFA, so the pattern can be matched efficiently
65/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
DFAs and NFAs
▶ NFAs and DFAs define the class of regular languages
▶ Each NFA can be transformed into a unique minimal DFA
▶ NFAs are often more intuitive to build and easier to understand
▶ DFA – especially minimal DFA – are more efficient to compute
▶ despite the fact they often have far more states than the NFA
▶ Regular languages are closed under the union, concatenation, star closure, intersection, and complement operations
▶ We use these to build the NFA, before converting to a minimal DFA
66/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions
▶ What they are and how to use them ▶ Regular operations
▶ Equivalence with DFA/NFA
67/67

Related Posts