Hierarchy of languages

1

Deterministic Finite State Automata (DFA)

……..

​

​

​

​

​

​

• One-way, infinite tape, broken into cells
• One-way, read-only tape head.
• Finite control, i.e.,
• finite number of states, and
• transition rules between them, i.e.,
• a program, containing the position of the read head, current symbol being scanned, and the current “state.”
• A string is placed on the tape, read head is positioned at the left end, and the DFA will read the string one symbol at a time until all symbols have been read. The DFA will then either accept or reject the string.

2

Finite

Control

• The finite control can be described by a transition diagram or table:

​

• Example #1:

​

​

​

​

​

​

​

1 0 0 1 1

q₀ q₀ q₁ q₀ q₀ q₀

​

• One state is final/accepting, all others are rejecting.
• The above DFA accepts those strings that contain an even number of 0’s, including the null string, over Sigma = {0,1}

L = {all strings with zero or more 0’s}

• Note, the DFA must reject all other strings

3

4

Note:

• Machine is for accepting a language, language is the purpose!

​

• Many equivalent machines may accept the same language,

but a machine cannot accept multiple languages!

​

​

​

​

• Id’s of the characters or states are irrelevant,

you can call them by any names!

Sigma = {0, 1} ≡ {a, b}

States = {q0, q1} ≡ {u, v}, as long as they have

identical (isomorphic) transition table

M1

M2

….

M-inf

L

• An equivalent machine to the previous example (DFA for even number of 0’s):

​

​

​

​

​

​

​

1 0 0 1 1

q₀ q₃ q₁ q₂ q₂ q₂ accept string

​

• One state is final/accepting, all others are rejecting.
• The above DFA accepts those strings that contain an even number of 0’s, including null string, over Sigma = {0,1}
• Can you draw a machine for a language by excluding the null string from the language? L = {all strings with 2 or more 0’s}

5

q₂

1

1

0

q₃

1

0

• Example #2:

​

​

​

​

​

a c c c b accepted

q₀ q₀ q₁ q₂ q₂ q₂

​

a a c rejected

q₀ q₀ q₀ q₁

​

• Accepts those strings that contain at least two c’s

6

7

Inductive Proof (sketch): that the machine correctly accepts strings with at least two c’s

Proof goes over the length of the string.

​

Base: x a string with |x|=0. state will be q0 => rejected.

Inductive hypothesis: |x|= integer k, & string x is rejected - in state q0 (x must have zero c),

OR, rejected – in state q1 (x must have one c),

OR, accepted – in state q2 (x has already with two c’s)

​

Inductive steps: Each case for symbol p, for string xp (|xp| = k+1), the last symbol p = a, b or c

​

​

​

​

​

​

​

​

Formal Definition of a DFA

• A DFA is a five-tuple:

​

M = (Q, Σ, δ, q₀, F)

​

Q A finite set of states

Σ A finite input alphabet

q₀ The initial/starting state, q₀ is in Q

F A set of final/accepting states, which is a subset of Q

δ A transition function, which is a total function from Q x Σ to Q

​

δ: (Q x Σ) –_> Q δ is defined for any q in Q and s in Σ, and

δ(q,s) = q’ is equal to some state q’ in Q, could be q’=q

​

Intuitively, δ(q,s) is the state entered by M after reading symbol s while in state q.

8

• Revisit example #1:

​

Q = {q₀, q₁}

Σ = {0, 1}

Start state is q₀

F = {q₀}

​

δ:

0 1

q₀ q₁ q₀

​

q₁ q₀ q₁

9

• Revisit example #2:

​

Q = {q₀, q₁, q₂}

Σ = {a, b, c}

Start state is q₀

F = {q₂}

​

δ: a b c

q₀ q₀ q₀ q₁

​

q₁ q₁ q₁ q₂

​

q₂ q₂ q₂ q₂

​

​

• Since δ is a function, at each step M has exactly one option.
• It follows that for a given string, there is exactly one computation.

10

Extension of δ to Strings

δ^{^} : (Q x Σ^*) –_> Q

​

δ^{^}(q,w) – The state entered after reading string w having started in state q.

​

​

Formally:

​

1) δ^{^}(q, ε) = q, and

2) For all w in Σ^* and a in Σ

δ^{^}(q,wa) = δ (δ^{^}(q,w), a)

11

• Recall Example #1:

​

​

​

​

• What is δ^{^}(q₀, 011)? Informally, it is the state entered by M after processing 011 having started in state q_0.
• Formally:

​

δ^{^}(q₀, 011) = δ (δ^{^}(q₀,01), 1) by rule #2

= δ (δ ( δ^{^}(q₀,0), 1), 1) by rule #2

= δ (δ (δ (δ^{^}(q₀, λ), 0), 1), 1) by rule #2

= δ (δ (δ(q₀,0), 1), 1) by rule #1

= δ (δ (q₁, 1), 1) by definition of δ

= δ (q₁, 1) by definition of δ

= q₁ by definition of δ

​

• Is 011 accepted? No, since δ^{^}(q₀, 011) = q₁ is not a final state.

12

​

​

• Note that:

​

δ^{^} (q,a) = δ(δ^{^}(q, ε), a) by definition of δ^{^}, rule #2

= δ(q, a) by definition of δ^{^}, rule #1

​

• Therefore:

​

δ^{^} (q, a₁a₂…a_n) = δ(δ(…δ(δ(q, a1), a2)…), a_n)

​

​

• However, we will abuse notations, and use δ in place of δ^{^}:

​

δ^{^}(q, a₁a₂…a_n) = δ(q, a₁a₂…a_n)

13

• Example #3:

​

​

​

• What is δ(q₀, 011)? Informally, it is the state entered by M after processing 011 having started in state q_0.
• Formally:

δ(q₀, 011) = δ (δ(q₀,01), 1) by rule #2

= δ (δ (δ(q₀,0), 1), 1) by rule #2

= δ (δ (q₁, 1), 1) by definition of δ

= δ (q₁, 1) by definition of δ

= q₁ by definition of δ

​

• Is 011 accepted? No, since δ(q₀, 011) = q₁ is not a final state.
• Language?
• L ={ all strings over {0,1} that has 2 or more 0 symbols}

14

q₁

q₀

1

1

0

0

1

0

• Recall Example #3:

​

​

​

​

• What is δ(q₁, 10)?

​

δ(q₁, 10) = δ (δ(q₁,1), 0) by rule #2

= δ (q₁, 0) by definition of δ

= q₂ by definition of δ

​

• Is 10 accepted? No, since δ(q₀, 10) = q₁ is not a final state. The fact that δ(q₁, 10) = q₂ is irrelevant, q1 is not the start state!

15

0

0

Definitions related to DFAs

• Let M = (Q, Σ, δ,q₀,F) be a DFA and let w be in Σ^*. Then w is accepted by M iff δ(q₀,w) = p for some state p in F.

​

• Let M = (Q, Σ, δ,q₀,F) be a DFA. Then the language accepted by M is the set:

​

L(M) = {w | w is in Σ^* and δ(q₀,w) is in F}

​

• Another equivalent definition:

​

L(M) = {w | w is in Σ^* and w is accepted by M}

• Let L be a language. Then L is a regular language iff there exists a DFA M such that L = L(M).

​

• Let M₁ = (Q₁, Σ₁, δ₁, q₀, F₁) and M₂ = (Q₂, Σ₂, δ₂, p₀, F₂) be DFAs. Then M₁ and M₂ are equivalent iff L(M₁) = L(M₂).

16

​

• Notes:
• A DFA M = (Q, Σ, δ,q₀,F) partitions the set Σ^* into two sets: L(M) and

Σ^* - L(M).

​

• If L = L(M) then L is a subset of L(M) and L(M) is a subset of L (def. of set equality).

​

• Similarly, if L(M₁) = L(M₂) then L(M₁) is a subset of L(M₂) and L(M₂) is a subset of L(M₁).

​

• Some languages are regular, others are not. For example, if

​

Regular: L₁ = {x | x is a string of 0's and 1's containing an even number of 1's} and

​

Not-regular: L₂ = {x | x = 0ⁿ1ⁿ for some n >= 0}

​

• Can you write a program to “simulate” a given DFA, or any arbitrary input DFA?

​

• Question we will address later:
• How do we determine whether or not a given language is regular?

17

• Give a DFA M such that:

​

L(M) = {x | x is a string of 0’s and 1’s and |x| >= 2}

​

​

​

​

​

​

​

​

​

Prove this by induction

18

• Give a DFA M such that:

​

L(M) = {x | x is a string of (zero or more) a’s, b’s and c’s such

that x does not contain the substring aa}

​

​

​

​

​

​

Logic:

In Start state (q0): b’s and c’s: ignore – stay in same state

q0 is also “accept” state

First ‘a’ appears: get ready (q1) to reject

But followed by a ‘b’ or ‘c’: go back to start state q0

When second ‘a’ appears after the “ready” state: go to reject state q2

Ignore everything after getting to the “reject” state q2

19

• Give a DFA M such that:

​

L(M) = {x | x is a string of a’s, b’s and c’s such that x

contains the substring aba}

​

​

​

​

​

​

​

Logic: acceptance is straight forward, progressing on each expected symbol

However, rejection needs special care, in each state (for DFA, we will see this becomes easier in NFA, non-deterministic machine)

20

• Give a DFA M such that:

​

L(M) = {x | x is a string of a’s and b’s such that x

contains both aa and bb}

First do, for a language where ‘aa’ comes before ‘bb’

Then do its reverse; and then parallelize them.

​

​

​

​

​

​

​

​

​

Remember, you may have multiple “final” states, but only one “start” state

21

• Let Σ = {0, 1}. Give DFAs for {}, {ε}, Σ^*, and Σ⁺.

​

For {}: For {ε}:

​

​

​

​

​

​

For Σ^*: For Σ⁺:

22

0/1

• Problem: Third symbol from last is 1

23

Is this a DFA?

No, but it is a Non-deterministic Finite Automaton

Nondeterministic Finite State�Automata (NFA)

• An NFA is a five-tuple:

​

M = (Q, Σ, δ, q₀, F)

​

Q A finite set of states

Σ A finite input alphabet

q₀ The initial/starting state, q₀ is in Q

F A set of final/accepting states, which is a subset of Q

δ A transition function, which is a total function from Q x Σ to 2^Q

​

δ: (Q x Σ) –_> 2^Q :2^Q is the power set of Q, the set of all subsets of Q δ(q,s) :The set of all states p such that there is a transition

labeled s from q to p

δ(q,s) is a function from Q x S to 2^Q (but not only to Q)

24

• Example #1: one or more 0’s followed by one or more 1’s

​

Q = {q₀, q₁, q₂}

Σ = {0, 1}

Start state is q₀

F = {q₂}

​

δ: 0 1

q₀

​

q₁

​

q₂

​

​

​

25

q₁

q₀

0

1

0

1

0/1

• Example #2: pair of 0’s or pair of 1’s as substring

​

Q = {q₀, q₁, q₂ , q₃ , q₄}

Σ = {0, 1}

Start state is q₀

F = {q₂, q₄}

​

δ: 0 1

q₀

​

q₁

​

q₂

​

q₃

​

q₄

26

1

​

• Notes:
• δ(q,s) may not be defined for some q and s (what does that mean?)
• δ(q,s) may map to multiple q’s
• A string is said to be accepted if there exists a path from q₀ to some state in F
• A string is rejected if there exist NO path to any state in F
• The language accepted by an NFA is the set of all accepted strings

​

• Question: How does an NFA find the correct/accepting path for a given string?
• NFAs are a non-intuitive computing model
• You may use backtracking to find if there exists a path to a final state (following slide)
• Why NFA?
• We are primarily interested in NFAs as language defining capability, i.e., do NFAs accept languages that DFAs do not?
• Other secondary questions include practical ones such as whether or not NFA is easier to develop, or how does one implement NFA

​

​

27

​

• Determining if a given NFA (example #2) accepts a given string (001) can be done algorithmically:

​

​

q₀ q₀ q₀ q₀

​

q₃ q₃ q₁

​

q₄ q₄ accepted

​

• Each level will have at most n states:

Complexity: O(|x|*n), for running over a string x

28

0

0/1

0/1

​

• Another example (010):

​

​

q₀ q₀ q₀ q₀

​

q₃ q₁ q₃

​

not accepted

​

• All paths have been explored, and none lead to an accepting state.

29

0

​

• Question: Why non-determinism is useful?
• Non-determinism = Backtracking
• Compressed information
• Non-determinism hides backtracking
• Programming languages, e.g., Prolog, hides backtracking => Easy to program at a higher level: what we want to do, rather than how to do it
• Useful in algorithm complexity study

​

• Is NDA more “powerful” than DFA, i.e., accepts type of languages that any DFA cannot?

​

​

​

30

• Let Σ = {a, b, c}. Give an NFA M that accepts:

​

L = {x | x is in Σ^* and x contains ab}

​

​

​

​

​

​

​

Is L a subset of L(M)? Or, does M accepts all string in L?

Is L(M) a subset of L? Or, does M rejects all strings not in L?

​

• Is an NFA necessary? Can you draw a DFA for this L?
• Designing NFAs is not as trivial as it seems: easy to create bug accepting string outside language

31

• Let Σ = {a, b}. Give an NFA M that accepts:

​

L = {x | x is in Σ^* and the third to the last symbol in x is b}

​

​

​

​

​

​

​

Is L a subset of L(M)?

Is L(M) a subset of L?

​

• Give an equivalent DFA as an exercise.

32

Extension of δ to Strings and Sets of States

• What we currently have: δ : (Q x Σ) –_> 2^Q

​

• What we want (why?): δ : (2^Q x Σ^*) –_> 2^Q

​

• We will do this in two steps, which will be slightly different from the book, and we will make use of the following NFA.

​

33

Extension of δ to Strings and Sets of States

• Step #1:

​

Given δ: (Q x Σ) –_> 2^Q define δ^#: (2^Q x Σ) –_> 2^Q as follows:

​

1) δ^#(R, a) = δ(q, a) for all subsets R of Q, and symbols a in Σ

​

• Note that:

​

δ^#({p},a) = δ(q, a) by definition of δ^#, rule #1 above

= δ(p, a)

​

• Hence, we can use δ for δ^#

​

δ({q₀, q₂}, 0) These now make sense, but previously

δ({q₀, q₁, q₂}, 0) they did not.

34

​

• Example:

​

δ({q₀, q₂}, 0) = δ(q₀, 0) U δ(q₂, 0)

= {q₁, q₃} U {q₃, q₄}

= {q₁, q₃, q₄}

​

​

δ({q₀, q₁, q₂}, 1) = δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1)

= {} U {q₂, q₃} U {}

= {q₂, q₃}

​

​

​

​

35

• Step #2:

​

Given δ: (2^Q x Σ) –_> 2^Q define δ^{^}: (2^Q x Σ*) –_> 2^Q as follows:

​

δ^{^}(R,w) – The set of states M could be in after processing string w, having started from any state in R.

​

Formally:

​

2) δ^{^}(R, ε) = R for any subset R of Q

3) δ^{^}(R,wa) = δ (δ^{^}(R,w), a) for any w in Σ^*, a in Σ, and

subset R of Q

• Note that:

​

δ^{^}(R, a) = δ(δ^{^}(R, ε), a) by definition of δ^{^}, rule #3 above

= δ(R, a) by definition of δ^{^}, rule #2 above

​

• Hence, we can use δ for δ^{^}

​

δ({q₀, q₂}, 0110) These now make sense, but previously

δ({q₀, q₁, q₂}, 101101) they did not.

36

​

• Example:

​

​

​

​

​

​

​

​

​

What is δ({q₀}, 10)?

​

Informally: The set of states the NFA could be in after processing 10,

having started in state q₀, i.e., {q₁, q₂, q₃}.

​

Formally: δ({q₀}, 10) = δ(δ({q₀}, 1), 0)

= δ({q₀}, 0)

= {q₁, q₂, q₃}

Is 10 accepted? Yes!

37

​

• Example:

​

What is δ({q₀, q₁}, 1)?

​

δ({q₀ , q₁}, 1) = δ({q₀}, 1) ∪ δ({q₁}, 1)

= {q₀} ∪ {q₂, q₃}

= {q₀, q₂, q₃}

​

​

What is δ({q₀, q₂}, 10)?

​

δ({q₀ , q₂}, 10) = δ(δ({q₀ , q₂}, 1), 0)

= δ(δ({q₀}, 1) U δ({q₂}, 1), 0)

= δ({q₀} ∪ {q₃}, 0)

= δ({q₀,q₃}, 0)

= δ({q₀}, 0) ∪ δ({q₃}, 0)

= {q₁, q₂, q₃} ∪ {}

= {q₁, q₂, q₃}

38

​

• Example:

​

δ({q₀}, 101) = δ(δ({q₀}, 10), 1)

= δ(δ(δ({q₀}, 1), 0), 1)

= δ(δ({q₀}, 0), 1)

= δ({q₁ , q₂, q₃}, 1)

= δ({q₁}, 1) U δ({q₂}, 1) U δ({q₃}, 1)

= {q₂, q₃} U {q₃} U {}

= {q₂, q₃}

​

Is 101 accepted? Yes! q₃ is a final state.

39

Definitions for NFAs

• Let M = (Q, Σ, δ,q₀,F) be an NFA and let w be in Σ^*. Then w is accepted by M iff δ({q₀}, w) contains at least one state in F.

​

• Let M = (Q, Σ, δ,q₀,F) be an NFA. Then the language accepted by M is the set:

​

L(M) = {w | w is in Σ^* and δ({q₀},w) contains at least one state in F}

​

• Another equivalent definition:

​

L(M) = {w | w is in Σ^* and w is accepted by M}

​

40

Equivalence of DFAs and NFAs

• Do DFAs and NFAs accept the same class of languages?
• Is there a language L that is accepted by a DFA, but not by any NFA?
• Is there a language L that is accepted by an NFA, but not by any DFA?

​

• Observation: Every DFA is an NFA, DFA is only restricted NFA.

​

• Therefore, if L is a regular language then there exists an NFA M such that L = L(M).

​

• It follows that NFAs accept all regular languages.

​

• But do NFAs accept more?

41

• Consider the following DFA: 2 or more c’s

​

Q = {q₀, q₁, q₂}

Σ = {a, b, c}

Start state is q₀

F = {q₂}

​

δ: a b c

q₀ q₀ q₀ q₁

​

q₁ q₁ q₁ q₂

​

q₂ q₂ q₂ q₂

​

42

• An Equivalent NFA:

​

Q = {q₀, q₁, q₂}

Σ = {a, b, c}

Start state is q₀

F = {q₂}

​

δ: a b c

q₀ {q₀} {q₀} {q₁}

​

q₁ {q₁} {q₁} {q₂}

​

q₂ {q₂} {q₂} {q₂}

​

43

​

• Lemma 1: Let M be an DFA. Then there exists a NFA M’ such that L(M) = L(M’).

​

• Proof: Every DFA is an NFA. Hence, if we let M’ = M, then it follows that L(M’) = L(M).

​

The above is just a formal statement of the observation from the previous slide.

​

44

​

• Lemma 2: Let M be an NFA. Then there exists a DFA M’ such that L(M) = L(M’).

​

• Proof: (sketch)

​

Let M = (Q, Σ, δ,q₀,F).

​

Define a DFA M’ = (Q’, Σ, δ’,q^’₀,F’) as:

​

Q’ = 2^Q Each state in M’ corresponds to a

= {Q₀, Q₁,…,} subset of states from M

​

where Q_u = [q_i0, q_i1,…q_ij]

​

F’ = {Q_u | Q_u contains at least one state in F}

​

q^’₀ = [q₀]

​

δ’(Q_u, a) = Q_v iff δ(Q_u, a) = Q_v

45

• Example: empty string or start and end with 0

​

Q = {q₀, q₁}

Σ = {0, 1}

Start state is q₀

F = {q₀}

​

δ: 0 1

q₀

​

q₁

​

​

​

​

46

q₁

0

0/1

0

• Example of creating a DFA out of an NFA (as per the constructive proof):

​

​

​

-->q₀

​

δ for DFA: 0 1 q₁

->q₀

​

​

[q₁]

[ ]

​

​

​

47

q₁

0

0/1

0

• Example of creating a DFA out of an NFA (as per the constructive proof):

​

​

​

​

​

δ: 0 1

->q₀

​

​

[q₁]

​

[ ]

[q₀₁]

​

​

48

q₁

0

0/1

0

• Example of creating a DFA out of an NFA (as per the constructive proof):

​

​

​

​

​

δ: 0 1

->q₀

​

​

[q₁]

​

[ ]

[q₀₁]

​

​

49

q₁

0

0/1

0

• Example of creating a DFA out of an NFA (as per the constructive proof):

​

​

​

​

​

δ: 0 1

->q₀

​

​

[q₁]

​

[ ]

[q₀₁]

​

​

50

q₁

0

0/1

0

• Construct DFA M’ as follows:

​

​

​

​

​

​

​

​

​

​

​

​

δ({q₀}, 0) = {q₁} => δ’([q₀], 0) = [q₁]

δ({q₀}, 1) = {} => δ’([q₀], 1) = [ ]

δ({q₁}, 0) = {q₀, q₁} => δ’([q₁], 0) = [q₀q₁]

δ({q₁}, 1) = {q₁} => δ’([q₁], 1) = [q₁]

δ({q₀, q₁}, 0) = {q₀, q₁} => δ’([q₀q₁], 0) = [q₀q₁]

δ({q₀, q₁}, 1) = {q₁} => δ’([q₀q₁], 1) = [q₁]

δ({}, 0) = {} => δ’([ ], 0) = [ ]

δ({}, 1) = {} => δ’([ ], 1) = [ ]

51

[ ]

1

0

1

[q₁]

0

0/1

1

0

​

• Theorem: Let L be a language. Then there exists an DFA M such that L = L(M) iff there exists an NFA M’ such that L = L(M’).

​

• Proof:

(if) Suppose there exists an NFA M’ such that L = L(M’). Then by Lemma 2 there exists an DFA M such that L = L(M).

​

(only if) Suppose there exists an DFA M such that L = L(M). Then by Lemma 1 there exists an NFA M’ such that L = L(M’).

​

• Corollary: The NFAs define the regular languages.

52

​

• Note: Suppose R = {}

​

δ(R, 0) = δ(δ(R, ε), 0)

= δ(R, 0)

= δ(q, 0)

= {} Since R = {}

​

​

• Exercise - Convert the following NFA to a DFA:

​

Q = {q₀, q₁, q₂} δ: 0 1

Σ = {0, 1}

Start state is q₀ q₀

F = {q₀}

q₁

​

q₂

​

53

• Problem: Third symbol from last is 1

54

Now, can you convert this NFA to a DFA?

NFAs with ε Moves

• An NFA-ε is a five-tuple:

​

M = (Q, Σ, δ, q₀, F)

​

Q A finite set of states

Σ A finite input alphabet

q₀ The initial/starting state, q₀ is in Q

F A set of final/accepting states, which is a subset of Q

δ A transition function, which is a total function from Q x Σ U {ε} to 2^Q

​

δ: (Q x (Σ U {ε})) –_> 2^Q

δ(q,s) -The set of all states p such that there is a

transition labeled a from q to p, where a

is in Σ U {ε}

• Sometimes referred to as an NFA-ε other times, simply as an NFA.

55

• Example:

​

​

​

​

​

​

​

δ: 0 1 ε

q₀ - A string w = w₁w₂…w_n is processed

as w = ε^*w₁ε^*w₂ε^* … ε^*w_nε^*

q₁ - Example: all computations on 00:

0 ε 0

q₂ q₀ q₀ q₁ q₂

:

q₃

​

56

Informal Definitions

• Let M = (Q, Σ, δ,q₀,F) be an NFA-ε.

​

• A String w in Σ^* is accepted by M iff there exists a path in M from q₀ to a state in F labeled by w and zero or more ε transitions.

​

• The language accepted by M is the set of all strings from Σ^* that are accepted by M.

​

57

ε-closure

• Define ε-closure(q) to denote the set of all states reachable from q by zero or more ε transitions.

​

• Examples: (for the previous NFA)

​

ε-closure(q₀) = {q₀, q₁, q₂} ε-closure(q₂) = {q₂}

ε-closure(q₁) = {q₁, q₂} ε-closure(q₃) = {q₃}

​

• ε-closure(q) can be extended to sets of states by defining:

​

ε-closure(P) = ε-closure(q)

​

• Examples:

​

ε-closure({q₁, q₂}) = {q₁, q₂}

ε-closure({q₀, q₃}) = {q₀, q₁, q₂, q₃}

58

Extension of δ to Strings and Sets of States

• What we currently have: δ : (Q x (Σ U {ε})) –_> 2^Q

​

• What we want (why?): δ : (2^Q x Σ^*) –_> 2^Q

​

• As before, we will do this in two steps, which will be slightly different from the book, and we will make use of the following NFA.

​

59

• Step #1:

​

Given δ: (Q x (Σ U {ε})) –_> 2^Q define δ^#: (2^Q x (Σ U {ε})) –_> 2^Q as follows:

​

1) δ^#(R, a) = δ(q, a) for all subsets R of Q, and symbols a in Σ U {ε}

​

• Note that:

​

δ^#({p},a) = δ(q, a) by definition of δ^#, rule #1 above

= δ(p, a)

​

• Hence, we can use δ for δ^#

​

δ({q₀, q₂}, 0) These now make sense, but previously

δ({q₀, q₁, q₂}, 0) they did not.

60

​

• Examples:

​

What is δ({q₀ , q₁, q₂}, 1)?

​

δ({q₀ , q₁, q₂}, 1) = δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1)

= { } U {q₀, q₃} U {q₂}

= {q₀, q₂, q₃}

​

​

What is δ({q₀, q₁}, 0)?

​

δ({q₀ , q₁}, 0) = δ(q₀, 0) U δ(q₁, 0)

= {q₀} U {q₁, q₂}

= {q₀, q₁, q₂}

61

​

​

• Step #2:

​

Given δ: (2^Q x (Σ U {ε})) –_> 2^Q define δ^{^}: (2^Q x Σ^*) –_> 2^Q as follows:

​

δ^{^}(R,w) – The set of states M could be in after processing string w, having starting from any state in R.

​

Formally:

​

2) δ^{^}(R, ε) = ε-closure(R) - for any subset R of Q

3) δ^{^}(R,wa) = ε-closure(δ(δ^{^}(R,w), a)) - for any w in Σ^*, a in Σ, and

subset R of Q

​

• Can we use δ for δ^{^}?

62

• Consider the following example:

​

δ({q₀}, 0) = {q₀}

​

δ^{^}({q₀}, 0) = ε-closure(δ(δ^{^}({q₀}, ε), 0)) By rule #3

= ε-closure(δ(ε-closure({q₀}), 0)) By rule #2

= ε-closure(δ({q_0, q₁, q₂}, 0)) By ε-closure

= ε-closure(δ(q₀, 0) U δ(q₁, 0) U δ(q₂, 0)) By rule #1

= ε-closure({q₀} U {q₁, q₂} U {q₂})

= ε-closure({q₀, q₁, q₂})

= ε-closure({q₀}) U ε-closure({q₁}) U ε-closure({q₂})

= {q₀, q₁, q₂} U {q₁, q₂} U {q₂}

= {q₀, q₁, q₂}

​

• So what is the difference?

​

δ(q₀, 0) - Processes 0 as a single symbol, without ε transitions.

δ^{^}(q₀ , 0) - Processes 0 using as many ε transitions as are possible.

63

​

• Example:

​

δ^{^}({q₀}, 01) = ε-closure(δ(δ^{^}({q₀}, 0), 1)) By rule #3

= ε-closure(δ({q₀, q₁, q₂}), 1) Previous slide

= ε-closure(δ(q₀, 1) U δ(q₁, 1) U δ(q₂, 1)) By rule #1

= ε-closure({ } U {q₀, q₃} U {q₂})

= ε-closure({q₀, q₂, q₃})

= ε-closure({q₀}) U ε-closure({q₂}) U ε-closure({q₃})

= {q₀, q₁, q₂} U {q₂} U {q₃}

= {q₀, q₁, q₂, q₃}

64

Definitions for NFA-ε Machines

• Let M = (Q, Σ, δ,q₀,F) be an NFA-ε and let w be in Σ^*. Then w is accepted by M iff δ^{^}({q₀}, w) contains at least one state in F.

​

• Let M = (Q, Σ, δ,q₀,F) be an NFA-ε. Then the language accepted by M is the set:

​

L(M) = {w | w is in Σ^* and δ^{^}({q₀},w) contains at least one state in F}

​

• Another equivalent definition:

​

L(M) = {w | w is in Σ^* and w is accepted by M}

​

65

Equivalence of NFAs and NFA-εs

• Do NFAs and NFA-ε machines accept the same class of languages?
• Is there a language L that is accepted by a NFA, but not by any NFA-ε?
• Is there a language L that is accepted by an NFA-ε, but not by any DFA?

​

• Observation: Every NFA is an NFA-ε.

​

• Therefore, if L is a regular language then there exists an NFA-ε M such that L = L(M).

​

• It follows that NFA-ε machines accept all regular languages.

​

• But do NFA-ε machines accept more?

66

​

• Lemma 1: Let M be an NFA. Then there exists a NFA-ε M’ such that L(M) = L(M’).

​

• Proof: Every NFA is an NFA-ε. Hence, if we let M’ = M, then it follows that L(M’) = L(M).

​

The above is just a formal statement of the observation from the previous slide.

​

67

​

• Lemma 2: Let M be an NFA-ε. Then there exists a NFA M’ such that L(M) = L(M’).

​

• Proof: (sketch)

​

Let M = (Q, Σ, δ,q₀,F) be an NFA-ε.

​

Define an NFA M’ = (Q, Σ, δ’,q₀,F’) as:

​

F’ = F U {q} if ε-closure(q) contains at least one state from F

F’ = F otherwise

​

δ’(q, a) = δ^{^}(q, a) - for all q in Q and a in Σ

​

• Notes:
• δ’: (Q x Σ) –_> 2^Q is a function
• M’ has the same state set, the same alphabet, and the same start state as M
• M’ has no ε transitions

68

• Example:

​

​

​

​

​

​

​

• Step #1:
• Same state set as M
• q₀ is the starting state

69

• Example:

​

​

​

​

​

​

​

• Step #2:
• q₀ becomes a final state

70

q₁

q₃

• Example:

​

​

​

​

​

​

​

• Step #3:

71

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₁

q₃

0

0

0

• Example:

​

​

​

​

​

​

​

• Step #4:

72

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₁

q₃

0/1

0/1

0/1

1

• Example:

​

​

​

​

​

​

​

• Step #5:

73

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₁

q₃

0/1

0/1

0/1

1

0

0

• Example:

​

​

​

​

​

​

​

• Step #6:

74

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₁

q₃

0/1

0/1

0/1

1

0/1

0/1

1

1

• Example:

​

​

​

​

​

​

​

• Step #7:

75

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₃

0/1

0/1

0/1

1

0/1

0/1

1

1

0

q₁

• Example:

​

​

​

​

​

​

​

• Step #8: [use table of e-closure]
• Done!

76

q₀

ε

0/1

1

0

q₁

0

q₃

ε

0

1

q₁

q₃

0/1

0/1

0/1

1

0/1

0/1

1

1

0/1

​

• Theorem: Let L be a language. Then there exists an NFA M such that L= L(M) iff there exists an NFA-ε M’ such that L = L(M’).

​

• Proof:

(if) Suppose there exists an NFA-ε M’ such that L = L(M’). Then by Lemma 2 there exists an NFA M such that L = L(M).

​

(only if) Suppose there exists an NFA M such that L = L(M). Then by Lemma 1 there exists an NFA-ε M’ such that L = L(M’).

​

• Corollary: The NFA-ε machines define the regular languages.

77