Part 1: Automata and Languages

Chapter 1: Regular Languages

Section 1.2: Nondeterminism

Nondeterminism: An Example

• Let L₁ = {0w| w is any string}.


• Let L₂ = {x0 | x is any string}.


• Let L₃ = L₁ ∪ L₂.


• Problem: Find M₃, such that L(M₃) = L₃
• Assume Σ = {0, 1}


• Solution:
• Find M₁ = ???
• Find M₂ = ???
• Now, M₃ = ...
• Easy!

Nondeterminism: Some Key Points

1. For some problems, it's much easier to find a NFA than a DFA
• NFA = Nondeterministic Finite Automata


2. We will show: Language L is regular iff it is recognized by a NFA!!!
• That is, NFA and DFA have the same power: if you can define a language with one you can define it with the other
• It's obvious that an NFA can define any language that a DFA can
• We will prove that a DFA can define any language that an NFA can!


3. We will have to develop a new formal definition for an NFA and its computation

Nondeterminism: Characteristics of NFAs

• NFA: Nondeterministic Finite Automata
• Basic Idea: A machine can have a choice on the next state for a given input symbol:


• Each state may have
• any number (ie 0, 1, 2, ...) of out transitions for a given input symbol


• Transitions that are ε transitions.
• These don't consume an input symbol!
• Thus, there may be a choice of whether or not to consume input


• Summary:
• each state may have 0, 1, or many exiting arrows for EACH input symbol
• an arrow can be marked with ε!


• Bottom line: the next state may NOT be completely determined by the current state and current input


• Example: Figure 1.27, page 48 (all strings with either ...)

DFA - For comparison

• The Finite Automata that we have studied so far are also called DFA (Deterministic Finite Automata)


• In a DFA, each state has a single transition out for each symbol in Σ


• In a DFA, the next state is completely determined by the current state and current input

NFA Computation - Intuition

• What does it mean to have a computation in a NFA?


• There are three interpretations of what the machine does when a choice occurs during a computation:


1. The machine makes a copy of itself for each possible branch! Each copy proceeds independently.


2. The computation forks (ie the machine continues execution in multiple states at one time!)


3. The machine guesses to find the path that accepts the string, if there is one
   • to guess correctly, it helps to have an omniscient human guiding the computation


• In each interpretation, the machine may or may not consume input when it makes a transition.


• If no transition is possible at a particular point in a particular computation, then that computation/copy dies (ie no longer exists)


• A machine accepts a string if any copy/computation accepts that string


• Example: Figures 27, 28, 29, pages 48, 49
• Example: 1.31 with 01101, page 51
• Example: 1.36 with baabaa, page 53

NFA: Some More Examples

• More examples showing how NFA work and that an creating an NFA is sometimes much simpler than creating a DFA


• Example NFA and equivalent DFA: 1.31, 1.32 (page 51): recognize strings with 1 in third from last position


• Remember: Assume machine guesses which path to take


• Example: 1.33 (p 52) - accepts 0^k, where k ≥ 0 is divisible by 2 or 3


• Remember: we will see that DFAs and NFAs are equivalent in power

NFA - Formal Definition

• Example 1.38, page 54


• Only difference in formal definition of DFA and NFA is in δ:
• δ: Q x Σ_ε → P(Q)
• Σ_ε = Σ ∪ {ε}
• What is δ for a DFA?


• If δ(q, y) = {}, then we don't draw an arrow.
• Remember: δ is defined for all elements of Q x Σ_ε

Thinking about Σ_ε

• What is ε?
• Is ε ∈ Σ?


• Is ε a symbol in Σ?


• Is ε ∈ Σ*? (hmmm, what do we mean by Σ* ?)
• Is Σ a language?
• If not, then Σ* is a shorthand for {w| ... }*


• Σ is a set of symbols; ε is a metasymbol that represents a string of no symbols


• ε is not a symbol that can appear in a string
• ε denotes a string
• However, we can write a string as a concatenation of symbols and ε

NFA: Formal Definition

1. Q is a finite set called the states


2. Σ is a finite set called the alphabet


3. δ: Q × Σ_ε → P(Q) is the transition function


4. q₀ ∈ Q is the start state


5. F ⊆ Q is the set of accept states

NFA Computation: Formal Definition

• Let M = ( Q, Σ, δ, q₀, F) be a FSM


• Let w be a string from the alphabet Σ


• Then M accepts w iff
  1. w can be written as w = y₁y₂ ... y_m where y_i ∈ Σ_ε, for i in 1 .. m
  2. and there is a sequence of states r₀, r₁, ... r_m
  such that
1. r₀ = q₀


2. r_i+1 ∈ δ(r_i , y_i+1) for i in 0 .. m-1


3. r_m ∈ F


• Consider Example 1.38, page 54


• How does this differ from DFA computation?


• Remember: y_i can be ε
• |w| ≤ m
• Also, we can do concatenation of any combination of symbols and strings.

NFA: Equivalence with DFA

• Each DFA is (obviously) an NFA


• Each NFA can be converted to a DFA!


• DFAs and NFAs are equivalent
• What does this imply about regular languages?

Theorem 1.39: NFAs and DFAs are Equivalent!

• DFA and NFA recognize the same set of languages!


• That is, NFA recognize exactly the regular languages


• Two machines are equivalent if they recognize the same language


• Theorem 1.39: Every NFA has an equivalent deterministic DFA (page 55)


• Proof idea: DFA operates on sets of states

Example of Proof 1.39 Construction

• Example of construction: Example 1.41, page 57
• Construct DFA M= (Q´,Σ´,δ´,q₀´,F´) equivalent to NFA N= (Q,Σ,δ,q₀,F)
• N has 3 states, M has 8 states
• Transition:
• What is transition δ({2}, b)?
• What is transition δ({2}, a)?
• What is transition δ({1}, b)?
• What is transition δ({1}, a)?
• What is transition δ({3}, b)?
• What is transition δ({3}, a)?
• Follow ε after input is read/followed
• What other transitions are there?
• What is the start state: E(q₀)


• Does the constructed machine recognize the same language?

Proof of Theorem 1.39

• Proof: See book (p. 55)
• First assume no ε transitions
• Next assume ε transitions exist
• Follow ε transitions after reading input
• Extend δ with function E that includes ε transitions
• Extend the start state to be E(q₀)


• Does the constructed machine recognize the same language?
• Formally we need a proof (inductive on the length of the computation), but informally, it's obvious that it works.

Corollary 1.40: NFAs recognize Regular Languages

• A language is regular iff some NFA recognizes it


• if ...


• only if ...

Theorem 1.45:

Regular Languages Closed under Union

• Theorem 1.45: The class of Regular Languages is closed under the union operation


• Theorem 1.45 (restated): If A and B are regular languages, then so is A ∪ B


• Proof Idea: Use NFAs for A and B to create a machine that recognizes the union
• What is the formal definition of the new machine?

Theorem 1.47:

Regular Languages Closed under Concatenation

• Theorem 1.47: The class of Regular Languages is closed under the concatenation operation


• Theorem 1.47 (restated): If A and B are regular languages, then so is A ο B


• Proof Idea: Use NFAs for A and B to create a machine that recognizes the concatenation
• What is the formal definition of the new machine?

Theorem 1.49:

Regular Languages Closed under Star

• Theorem 1.49: The class of Regular Languages is closed under the star operation


• Theorem 1.49 (restated): If A is a regular language, then so is A*


• Proof Idea: Use NFA for A to create a machine that recognizes the A*
• (Careful, this one has some subtleties)
• What is the formal definition of the new machine?