Week 2

CS240 • Language Theory and Automata • Fall 2006

Deterministic and Non-deterministic Finite Automata

Transition Diagram

Finite Automata • A formal way to describe certain simple, but highly useful languages called regular languages. • A graph with a finite number of nodes, called states sometimes called ``finite state machines”. • Arcs are labeled with one or more symbols from some alphabet. • One state is designated the start state or initial state. • Some states are final states or accepting states. • The language of the FA is the set of strings that label paths that go from the start state to some accepting state.

Example 1

• An FA can be represented by a graph: – nodes = states – arc from q to p is labeled by the set of input symbols a such that !(q, a) = p. – No arc if no transition from state q on input a. – Start state indicated by an arrow coming out of nowhere – Accepting states get double circles.

Give sequence of states visited on input string ababb Reading each letter of input string causes state transition

If path traveled when reading input string ends in a final state, string is accepted (recognized)

Example 1 (cont.)

On input string ababb : 1. start in state q0 2. read a, stay in state q0 3. read b, go to q1 4. read a, go to q0 5. read b, go to q1 6. read b, go to q2

Example 2

Example 1 (cont.)

Describe the language of machine. If machine is called M, then we specify the language L(M) L(M) = {w | w contains substring bb, for all w # {a,b}}

FA that recognizes simple identifiers start

letter

letter or digit

other character (delimeter)

L(M) = {???} L(M) = { " or all strings over alphabet {0,1} that end in 0}

FA for Newspaper Vending Machine

FA for coin flipping

quarter

• Four ways of arranging two coins, depending on which is heads (H) and which is tails (T)

quarter dime

dime

dime, quarter

dime

start

0

5 nickel

10 nickel

15 nickel

20 nickel

– HH, HT, TT, TH

25 nickel, dime, quarter

Model Problem as an FA HH: Flip first coin a

HH b

b

b

HT

a

HH: Flip second coin

TH

a

b

TH: Flip first coin TH: Flip second coin HT: Flip first coin HT: Flip second coin

TT

a Final state

– Flip the first coin (a) – Flip the second coin (b)

• Assume initially coins are laid out as HH • What are all possible ways of applying the operations so that the configuration is TT?

quarter

start

• Two operations:

TT: Flip first coin TT: Flip second coin

Conventions • It helps if we can avoid mentioning the type of every name by following some rules: – Input symbols are a, b, etc., or digits. – Strings of input symbols are u, v, . . . , z. – States are q, p, etc.

Formal Definition of Deterministic Finite Automaton (DFA) • • • • •

Finite set of states, typically Q. Finite alphabet of input symbols, typically $. One state is the start/initial state, often called q0. Zero or more final/accepting states, the set is typically F. A transition function, typically !. This function: – Takes a state and input symbol as arguments. – Transition function works over all possible state, symbol pairs to returns a state ( ! : Q % $ & Q ) <-- this makes it a DFA – One "rule" of ! would be written (q, a) = p, where q and p are states, and a is an input symbol. – Intuitively: if the FA is in state q, and input a is received, then the FA goes to state p (note: q = p OK).

Creating a Finite Automaton • If you think of the states as “memory”, then the memory of an FA is limited to the number of states. • The consequence of a finite number of states is, if |w| > number of states, some state must be repeated in the execution of the FA over w. • If the machine can’t remember all the symbols it has seen so far in an input string, it has to change state based on other information, e.g., L1 = the set of all strings with an odd number of 1’s over the alphabet {0,1}.

Any FA is represented as the five-tuple: A = (Q, $, !, q0 , F).

Creating a Finite Automaton • Start by putting yourself in the place of the FA that has to make every transition choice based on a single character, because it can’t look ahead or rewind. 1. Define the meaning of the states: – For L1, we can designate a two state automaton; one state applies to the situation in which the number of ones seen is even (so far), and the other to the situation where the number of ones seen is odd (so far).

2. Determine the transition function: – In either state, if you read a 0, stay put. Whenever you read a 1, follow a link to the other node.

3. Label the start state and final states. DONE? Not quite...

Creating a Finite Automaton 4.

Test your FA. A tool like JFLAP can help testing input strings on complex FAs

Example: Create an FA that accepts all the strings over alphabet {0,1} such that the string contains the substring 100. • Define the states. • Determine the transition function for each state. • Label the start state and the final states.

Example: Clamping Logic • A "clamping" circuit waits for a 1 input, and forever after makes a 1 output. However, to avoid clamping on spurious noise, we'll design an FA that waits for two 1's in a row, and "clamps" only then. • Shows how a state can represent the history of what has been seen on the input so far.

Transition Graph for Clamping Circuit

• The states we need are: – State q0, the start state, says that the most recent input (if there was one) was not a 1, and we have never seen two 1's in a row. – State q1 says we have never seen 11, but the previous input was 1. – State q2 is the only accepting state, it says that we have at some time seen 11. – Thus, A = ({q0, q1, q2}, {0, 1}, !, q0, {q2}), where ! is given by:

>q0 q1 *q2

0

1

q0 q0 q2

q1 q2 q2

By marking the start state with > and accepting states with *, the transition table that defines ! also specifies the entire FA

Proving a given language is regular To show a language L is regular, produce a DFA that recognizes L. For example, if L = { awa | w # {a,b}* }

Proving a given language is regular L = { w : |w| mod 3 = 0 for w # {a,b}* }

Extension of ! to Paths Intuitively, a FA accepts a string w = a1a2… an if there is a path in the transition diagram that: 1. Begins at the start state, 2. Ends at an accepting state, and 3. Has sequence of labels a1,a2 , … , an .

Regular Languages More formally, an FA M accepts a string w = a0,a1,a2,...,an if there exists a sequence of states r0,r1,r2, ...,rn in Q such that 1. r0 = q0, 2. !(ri, ai+1) = ri+1, for i = 0, ..., n-1, and 3. rn # F.

A language is called a regular language if some FA accepts it. So to prove a language is regular, we just have to create a FA that accepts it.

Regular Operations Union Concatenation Star Closure

Regular Operations Union – DFAs that recognize languages L1 and L2 can be combined to give a DFA that accepts the union of L1 and L2

Theorem: The class of regular languages is closed under union Proof is by construction: 1. Given regular languages A1 and A2, where A1 is recognized by some DFA M1 and A2 is recognized by DFA M2. 2. Construct M from M1 and M2 a. Make the states of M = Q1 X Q2 b. Alphabet of A1 and A2 can be same or different. c. Each transition in M is to the state labeled by the pair of states M1 and M2 entered by each machine on each symbol. d. Start state = (start state of M1, start state of M2) e. F = {(r1, r2) | r1# F1 or r2# F2}

Regular Operations Union – DFAs that recognize languages L1 and L2 can be combined to give a DFA that accepts the union of L1 and L2

Concatenation – Same can be shown for concatenation, and star closure, with one hitch...

Regular Operations Concatenation (and Star Closure) To construct a DFA that accepts A1 A2, can we use the same strategy as we did for the union operation? I.e., can we take the DFA that accepts A1 and make the final state of A1 a non-final state that has a transition to the start state of the DFA that accepts A2? No because a DFA cannot “guess” where the string from A1 ends and that of A2 begins...what to do?

Use a Nondeterministic FA!! In a NFA, there can be 0 or more transitions out of each state on each symbol of the alphabet.

How does an NFA compute? Instead of a sequential flow of computation, the NFA can branch out from every state where there is more than 1 choice of outgoing arrow and follow that set of arrows. Imagine that the machine splits into multiple copies of itself and follows all possible paths in parallel. If there is no arrow out of a particular state on a particular symbol in an NFA, that branch of computation dies in that state. If any copy of the machine ends in an accepting state after reading an input string, we say the NFA accepts the input string.

Non-deterministic Finite Automata (NFA) • Important tool for designing string processors, e.g., grep, lexical analyzers. • But "imaginary," in the sense that it has to be implemented deterministically on each root to leaf branch of computation.

NFA to recognize HTML lists • The following NFA, call it M, scans HTML documents, looking for a list of what could be title-author pairs, perhaps in a reading list for some literature course. • M accepts whenever it finds the end of a list. • In an application, the strings that matched the title (before 'by') and author (after 'by') might be stored in a table of title-author pairs being accumulated.

start

,



• 
  
  Any non-tag
  
  Formal Definition of Nondeterministic Finite Automaton (NFA)
  
  space
  
  • Finite set of states, Q. • Finite alphabet of input symbols, $. • A transition function, !. This function:
  
  b
  
  – Takes a state and an input symbol or " as arguments. – Transition function works over all possible state, symbol pairs to return a set of states ( ! : Q % {$} & P(Q) )
  
  
• y
  
  • q0 # Q is the start state. space
  
  

,



Any non-tag

NFAs and DFAs • It might seem that because there is a degree of choice available in an NFA that it might be more powerful than a DFA – That is, NFAs might be able to recognize languages a DFA could not

• But this is not the case!

• F ' Q is the set of final states. DFAs are a subset of NFA’s

Any FA is represented as the five-tuple: A = (Q, $, !, q0 , F).

Equivalence of NFAs and DFAs • NFAs and DFAs recognize the same class of languages • Useful: easier to specify an NFA for a language, convert to DFA Two machines are equivalent if they recognize the same language

Theorem Every non-deterministic finite automaton has an equivalent deterministic finite automaton

Proof Idea • If a language is recognized by an NFA, show the existence of a DFA that also recognizes it • Convert NFA to an equivalent DFA that simulates the NFA – Proof by construction

• Intuitively, can simulate the NFA by keeping track of all the states you can get to on a given input

Proof • •

–

1. 2.

Visual version

Let N = (Q,$,!,q0,F) be an NFA recognizing some language A Construct a DFA recognizing A M = (Q’,$,!’,q0’,F’)

5

Q’ = the set of subsets of Q -- P(Q) For R # Q’ and a # $ let !’(R,a) = {q # Q | q # !(r,a) for some r # R} –

–

If R is a state of M, it is also a set of states of N (because of 1 above). When M reads a symbol a in a state R, it shows where a takes each state in R. Because each state may go to a set of states, we take the union of all these sets. This can be written as:

q0={q0} •

–

!' (R, a) = U! (r, a) r"R

M starts in the state corresponding to the collection containing just the start state of N.

F’ = {R # Q’|R contains an accept state of N}. •

The machine M accepts if one of the possible states that N could be in at this point is an accept state.

b

a

1

b

6

b a b a

2

a

3

Start state q0= {1}

7 8 9

4

b

10

!(1,a)= {2,3} !(1,b)= {4}

!({7,9},a)= ) !({7,9},b)= ) !({5,6,8},a)= ) !({5,6,8},b)= ) !({10},a)= ) !({10},b)= )

!({2,3},a)= !({2},a) ( !({3},a) = ) ( {7,9} = {7,9} !({2,3},b)= !({2},b) ( !({3},b) = {5,6} ( {8} = {5,6,8} Final states F’= !({4},a)= ) {{5,6,8},{10}} !({4},b)= {10}

" Labels

The DFA !(1,a)={2,3} !(1,b)={4} !({2,3},a)={7,9} !({2,3},b)={5,6,8} !({4},a)=) !({4},b)={10} !({7,9},a)= ) !({7,9},b)= ) !({5,6,8},a)= ) !({5,6,8},b)= ) !({10},a)= ) !({10},b)= )

a

{7,9}

b

{5,6,8}

{2,3}

{1} b

a

a

{4}

a,b

a,b {)}

b

{10}

a,b

Start state q0={1} Final states F’={{5,6,8},{10}}

In an NFA (NFA- "), arrows can be labeled with the " symbol, meaning that a transition(s) can be made to the following state(s) after consuming an input, or from the start state without consuming an input symbol. The convention used in our book is to follow the arrow(s) with label " out of the state the NFA is in after a symbol has been read and the arrow labeled with that symbol has already been traversed.

" Labels For example, if a b was read in state q1, the machine could transition to either q2 or q3. But if an a was read in state q2, the computation would die.

" Labels If the link between q0 and q1 was labeled with an epsilon, the machine could transition to q1 without reading a symbol or it could stay in q0 and read an input symbol and then transition to q1.

"

Example

NFA With "-Transitions

0

• Allow " to be a label on arcs – Nothing else changes: acceptance of w is still the existence of a path from the start state to an accepting state with label w. – But " can appear on arcs, and means the empty string (i.e., no visible contribution to w) – When an arc labeled " is traversed, no input is consumed

DFAs and NFA-"’s • "-transitions are a convenience, but do not increase the power of FA's. • For any NFA-" there is an equivalent (i.e., accepts the same language) DFA • The construction is similar to the NFA-toDFA construction

q

1

r

"

s

"

0 1

" "

001 is accepted by the path q, s, r, q, r, s, with label 0 01 = 001.

Creating a DFA from a NFA-" (or, eliminating "-transitions) 1. Compute the "-closure for each state (set of states reachable from that state on "-transitions only). 2. Start state is "-CLOSE(q0) (called E({q0}) in book). 3. Compute ! for each a # $ and each set S (each of the "-CLOSE’d sets) as follows: ! If a state p # S can reach state q on input a (not "), then add a transition on input a from S to "-CLOSE(q). 4. The set of final states includes those sets that contain at least one accepting state of the NFA-".

Example 1. Compute "-closure for all states: ECLOSE(q) = {q} ECLOSE(r) = {r,s} ECLOSE(s) = {r,s}

0

q

1

r

Regular Operations

s

With NFAs, showing that regular languages are closed under star closure and concatenation is much easier.

"

0 1

2. Compute !: !({q},0) = ECLOSE({s})={r,s} !({q},1) = ECLOSE({r})={r,s} !({r,s},0) = ECLOSE({q})={q} !({r,s},1) = ECLOSE({q})={q} 3. Final states FD ={{r,s}}

"

Concatenation Given 2 NFAs, N1 and N2, where N1 recognizes language A1 and N2 recognizes language A2, A1A2 is formed by making all the final states of N1 non-final and linking them via " links to the start state of N2.

RESULTING DFA: q

0,1

r,s

0,1

The class of regular languages is closed under the union operation

Regular Operations

For two languages R1 and R2, take two NFAs N1 and N2 and combine them into one new NFA N. N must accept input if either N1 or N2 accepts input.

Star Closure Given an NFA, N that recognizes language A, the NFA to recognize language A* is formed by creating a new start state that is also a final state with " arc to the old start state. Then make " arcs to from all the old final states back to the start state.

N1

N

"

N2

"

The new machine guesses nondeterministically which of the two machines accepts the input

The class of regular languages is closed under the concatenation operation

The class of regular languages is closed under the star operation

For two languages R1 and R2, take two NFAs N1 and N2 and combine them sequentially into one new NFA N.

For a language R1, modify N1 to accept (R1)*.

N1 N2

N1

N

" "

The new machine guesses nondeterministically where to split the input in order to have a first part accepted by N1 and a second part accepted by N2.

N

"

" "

The new machine has the option of jumping back to the start state to read another piece that N1 accepts.

Q: Why not just make the start state of N1 a final state?