Slide 1
Algorithms and Decision Procedures for Regular Languages
Chapter 9
Decision Procedures
A decision procedure is an algorithm whose result is a Boolean value. It must:
● Halt
● Be correct
Important decision procedures exist for regular languages:
● Given an FSM M and a string s, does M accept s?
● Given a regular expression and a string w, does
generate w?
Membership
We can answer the membership question by running an FSM.
But we must be careful:
Membership
decideFSM(M: FSM, w: string) =
If ndfsmsimulate(M, w) accepts then return True
else return False.
decideregex(: regular expression, w: string) =
From , use regextofsm to construct an FSM M
such that L() = L(M).
Return decideFSM(M, w).
Emptiness, Finiteness, Equivalence
● Given an FSM M, is L(M) empty?
● Given an FSM M, is L(M) = M*?
● Given an FSM M, is L(M) finite?
● Given an FSM M, is L(M) infinite?
● Given two FSMs M1 and M2, are they equivalent?
Emptiness
Given an FSM M, is L(M) empty?
The simulation approach:
The graph analysis approach:
1. Let M = ndfsmtodfsm(M).
2. For each string w in * such that |w| < |KM | do:
Run decideFSM(M, w).
3. If M accepts at least one such string, return False. Else return True.
1. Mark all states that are reachable via some path from the
start state of M.
2. If at least one marked state is an accepting state, return False. Else return True.
Totality
Given an FSM M, is L(M) = M*?
1. Construct M to accept L(M).
2. Return emptyFSM(M ).
Finiteness
Given an FSM M, is L(M) finite?
The graph analysis approach:
Finiteness
Given an FSM M, is L(M) finite?
The graph analysis approach:
The mere presence of a loop does not guarantee that L(M) is infinite. The loop might be:
labeled only with ,
unreachable from the start state, or
not on a path to an accepting state.
Finiteness
Given an FSM M, is L(M) finite?
The graph analysis approach:
1. M = ndfsmtodfsm(M).
2. M = minDFSM(M).
3. Mark all states in M that are on a path to an accepting
state.
4. Considering only marked states, determine whether there
are any cycles in M.
5. If there are cycles, return False. Else return True.
Finiteness
Given an FSM M, is L(M) finite?
The simulation approach:
1. M = ndfsmtodfsm(M).
For each string w in * such that do:
Run decideFSM(M, w).
If M accepts at least one such string, return False.
Else return True.
|KM | |w| 2|KM | - 1
Equivalence
● Given two FSMs M1 and M2, are they equivalent? In
other words, is L(M1) = L(M2)?
Two solutions.
Equivalence
● Given two FSMs M1 and M2, are they equivalent? In
other words, is L(M1) = L(M2)?
equalFSMs1(M1: FSM, M2: FSM) =
1. M1 = buildFSMcanonicalform(M1).
2. M2 = buildFSMcanonicalform(M2).
3. If M1 and M2 are equal, return True, else return False.
Equivalence
● Given two FSMs M1 and M2, are they equivalent? In
other words, is L(M1) = L(M2)?
equalFSMs2(M1: FSM, M2: FSM) =
1. Construct MA to accept L(M1) - L(M2).
2. Construct MB to accept L(M2) - L(M1).
3. Construct MC to accept L(MA) L(MB).
4. Return emptyFSM(MC).
Observe that M1 and M2 are equivalent iff:
(L(M1) - L(M2)) (L(M2) - L(M1)) = .
Minimality
● Given DFSM M, is M minimal?
1. M = minDFSM(M).
2. If |KM| = |KM | return True; else return False.
Answering Specific Questions
Given two regular expressions 1 and 2, is:
(L(1) L(2)) – {} ?
1. From 1, construct an FSM M1 such that L(1) = L(M1).
2. From 2, construct an FSM M2 such that L(2) = L(M2).
3. Construct M such that L(M ) = L(M1) L(M2).
4. Construct M such that L(M) = {}.
5. Construct M such that L(M ) = L(M ) - L(M).
6. If L(M ) is empty return False; else return True.
Answering Specific Questions
Given two regular expressions 1 and 2, are there at least 3 strings that are generated by both of them?
Summary of Closure Properties
● Compute functions of languages defined as FSMs:
● Given FSMs M1 and M2, construct a FSM M3 such that
L(M3) = L(M1) L(M2).
● Given FSMs M1 and M2, construct a new FSM M3 such that
L(M3) = L(M1) L(M2).
● Given FSM M, construct an FSM M3 such that
L(M3) = (L(M))*.
● Given a DFSM M, construct an FSM M3 such that
L(M3) = L(M).
● Given two FSMs M1 and M2, construct an FSM M3 such that
L(M3) = L(M1) L(M2).
● Given two FSMs M1 and M2, construct an FSM M3 such that
L(M3) = L(M1) - L(M2).
● Given an FSM M, construct an FSM M3 such that
L(M3) = (L(M))R.
Summary of Decision Procedures
● Decision procedures that answer questions about languages
defined by FSMs:
● Given an FSM M and a string s, decide whether s is
accepted by M.
● Given an FSM M, decide whether L(M) is empty.
● Given an FSM M, decide whether L(M) is finite.
● Given two FSMs, M1 and M2, decide whether
L(M1) = L(M2).
● Given an FSM M, is M minimal?