ZeePedia

Concatenation of FAs

<< Kleene’s Theorem Part III
Closure of an FA >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 13
Reading Material
Chapter 7
Introduction to Computer Theory
Summary
Examples of Kleene's theorem part III (method 1) continued, Kleene's theorem part III (method 2:
Concatenation of FAs), Example of Kleene's theorem part III  (method 2 : Concatenation of FAs)
Note
It may be noted that the example discussed at the end of previous lecture, FA1 contains two states while FA2
contains three states. Hence the total number of possible combinations of states of FA1 and FA2, in sequence,
will be six. For each combination the transitions for both a and b can be determined, but using the method in the
example, number of states of FA3 was reduced to five.
Example
Let r1 = (a+b)*a and the corresponding FA1 be
a
b
a
x1-
x2+
b
also r2 = (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b) and FA2 be
a,b
y1-
y2+
a,b
FA corresponding to r1+r2 can be determined as
a
b
a,b
a
x1-
y1-
x2+
y2+
b
a,b
New States after reading
Old States
a
b
z1-∫(x1,y1)
(x2,y2) ∫z2
(x1,y2) ∫ z3
z2+∫(x2,y2)
(x2,y1) ∫z4
(x1,y1) ∫ z1
z3+ ∫(x1,y2)
(x2,y1) ∫z4
(x1,y1) ∫ z1
z4+ ∫(x2,y1)
(x2,y2) ∫ z2
(x1,y2) ∫ z3
a
z2+
z1-
b
a
a
b
b
a
z4+
z3+
b
Example
Let r1 = ((a+b)(a+b))* and the corresponding FA1 be
a,b
x1±
x2
a,b
38
img
Theory of Automata
(CS402)
also r2 = (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b) and FA2 be
a,b
y1-
y2+
a,b
FA corresponding to r1+r2 can be determined as
New States after reading
Old States
a
b
z1±∫(x1,y1)
(x2,y2) ∫z2
(x2,y2) ∫ z2
(x1,y1) ∫z1
(x1,y1) ∫ z1
z2+∫(x2,y2)
Hence the required FA will be as follows
a,b
z1±
z2+
a,b
Method2 (Concatenation of two FAs):
Using the FAs corresponding to r1 and r2, an FA can be built, corresponding to r1r2. This method can be
developed considering the following examples
Example
Let r1 = (a+b)*b defines L1 and FA1 be
b
a
b
x1-
x2+
a
*
*
and r2 = (a+b ) aa (a+b ) defines L2 and FA2 be
a,b
b
a
a
y3+
y2
y1-
b
Let FA3 be an FA corresponding to r1r2, then the initial state of FA3 must correspond to the initial state of FA1
and the final state of FA3 must correspond to the final state of FA2.Since the language corresponding to r1r2 is
the concatenation of corresponding languages L1 and L2, consists of the strings obtained, concatenating the
strings of L1 to those of L2 , therefore the moment a final state of first FA is entered, the possibility of the
initial state of second FA will be included as well.
Since, in general, FA3 will be different from both FA1 and FA2, so the labels of the states of FA3 may be
supposed to be z1,z2, z3, ..., where z1 stands for the initial state. Since z1 corresponds to the states x1, so there
will be two transitions separately for each letter read at z1. It will give two possibilities of states which
correspond to either z1 or different from z1. This process may be expressed in the following transition table for
all possible states of FA3
b
a
b
x1-
x2+
a
a,b
b
a
a
y3+
y2
y1-
b
39
img
Theory of Automata
(CS402)
New States after reading
Old States
a
b
x1∫z1
(x2,y1)∫ z2
z1-∫x1
z2∫(x2,y1)
(x1,y2)∫z3
(x2,y1)∫ z2
z3∫(x1,y2)
(x1,y3)∫z4
(x2,y1)∫ z2
z4+∫(x1,y3)
(x1,y3)∫ z4
(x2,y1,y3)∫ z5
z5+∫(x2,y1,y3)
(x1,y2 ,y3)∫ z6
(x2,y1,y3)∫ z5
z6+∫(x1,y2,y3)
(x1,y3)∫ z4
(x2 ,y1,y3)∫ z5
Hence the required FA will be as follows
b
a
z3
z2
b
a
b
a
z4+
z1-
a
a
b
b
z5+
z6+
b
a
Note: Another example is discussed in the next lecture.
40
Table of Contents:
  1. What does automata mean, Introduction to languages
  2. Kleene Star Closure, Recursive definition of languages
  3. Regular Expression, Recursive definition of Regular Expression
  4. Equivalent Regular Expressions
  5. Finite Automaton
  6. Equivalent FAs
  7. FA corresponding to finite languages
  8. Examples of TGs: accepting all strings
  9. Generalized Transition Graphs
  10. Nondeterminism, Kleene’s Theorem
  11. Proof(Kleene’s Theorem Part II)
  12. Kleene’s Theorem Part III
  13. Concatenation of FAs
  14. Closure of an FA
  15. Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
  16. NFA with Null String
  17. NFA and Kleene’s Theorem
  18. NFA corresponding to Concatenation of FAs
  19. Distinguishable strings and Indistinguishable strings
  20. Finite Automaton with output, Moore machine
  21. Mealy machine
  22. Equivalent machines
  23. Mealy machines in terms of sequential circuit
  24. Regular languages, Complement of a language
  25. Nonregular languages
  26. Pumping Lemma
  27. Pumping Lemma version II
  28. Pseudo theorem
  29. Decidability
  30. finiteness of a language
  31. Context Free Grammar (CFG), CFG terminologies
  32. Trees
  33. Polish Notation (o-o-o)
  34. Total language tree, Regular Grammar
  35. Null Production
  36. Chomsky Normal Form (CNF)
  37. A new format for FAs
  38. Nondeterministic PDA
  39. PDA corresponding to CFG
  40. Conversion form of PDA
  41. Conversion Form, Joints of the machine
  42. Row language, Nonterminals
  43. Non-Context-Free language, Pumping lemma for CFLs
  44. Decidablity, Parsing Techniques
  45. Turing machine