Kleene's Theorem and NFA: Asif Nawaz UIIT, PMAS-Arid Agriculture University Rawalpindi
Kleene's Theorem and NFA: Asif Nawaz UIIT, PMAS-Arid Agriculture University Rawalpindi
Kleene's Theorem and NFA: Asif Nawaz UIIT, PMAS-Arid Agriculture University Rawalpindi
(i) (r1)
(ii) r1r2
(iii) r1 + r2
(iv) r1*
Rule 1
• There is an FA that accepts any particular
letter of the alphabet.
Proof of rule 1
• If letter x is in ∑, then the following FA accepts
only the word x.
Rule 2
• If there is an FA called FA1 that accepts the
language defined by the regular expression
r1, and there is an FA called FA2 that accepts
the language defined by the regular
expression r2, then there is an FA that we
shall call FA3 that accepts the language
defined by the regular expression (r1 + r2).
Proof of Rule 2
• We shall show that FA3 exists by presenting an
algorithm showing how to construct FA3.
• Algorithm:
– Starting with two machines, FA1 with states x1; x2; x3;
…, and FA2 with states y1; y2; y3; …, we construct a
new machine FA3 with states z1; z2; z3; … where each
zi is of the form xsomething or ysomething.
– The combination state xstart or ystart is the start state of
the new machine FA3.
– If either the x part or the y part is a final state, then the
corresponding z is a final state.
Algorithm (cont.)
– To go from one state z to another by reading a
letter from the input string, we observe what
happens to the x part and what happens to the y
part and go to the new state z accordingly. We
could write this as a formula:
Remarks
• The new machine FA3 constructed by the above algorithm will
simultaneously keep track of where the input would be if it were
running on FA1 alone, and where the input would be if it were running
on FA2 alone.
• If a string traces through the new machine FA3 and ends up at a final
state, it means that it would also end at a final state either on machine
FA1 or on machine FA2. Also, any string accepted by either FA1 or FA2
will be accepted by this FA3. So, the language FA3 accepts is the
union of the languages accepted by FA1 and FA2, respectively.
• Note that since there are only finitely many states x’s and finitely
many states y’s, there can be only finitely many possible states z’s.
Example
• Consider the following two FAs:
Example
• Consider the following two FAs:
• FA2 accepts all words with an odd number of letters (odd length).
• Can you use the algorithm to build a machine FA3 that accepts all
words that either have an odd number of letters or end in a?
• Using the algorithm, we can produce FA3 that accepts all words that
either have an odd number of letters or end in a, as follows:
• The only state that is not a + state is the - state. To get back to that
start state, a word must have an even number of letters and end in b.
Rule 3
If there is an FA1 that accepts the language
defined by the regular expression r1, and
there is an FA2 that accepts the language
defined by the regular expression r2, then
there is an FA3 that accepts the language
defined by the (concatenation) regular
expression (r1r2), i.e. the product language.
Algorithm
• First, create a state z for every state of FA1 that we may
go through before arriving at a final state.
2. For each final state xfinal of FA1, add a state z = xfinal or y1,
where y1 is the start state of FA2.
3. From the states added in step 2, add states
Example
• This machine accepts all words that both begin and end with the
letter b, which is what the product of the two languages (defined by
FA1 and FA2 respectively) would be.
• If you multiply the two languages in opposite order (i.e. first FA2 then
FA1), then the product language will be different. What is that
language? Can you build a machine for that product language