ZeePedia

finiteness of a language

<< Decidability
Context Free Grammar (CFG), CFG terminologies >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 30
Reading Material
Introduction to Computer Theory
Chapter 11,12
Summary
Deciding whether two languages are equivalent or not, example, deciding whether an FA accept any string or
not, method 3, examples, finiteness of a language
Example
Consider two languages L1 and L2, expressed by the REs r1=a* and r2=Y+aa* respectively. To determine
whether L1 and L2 are equivalent, let the corresponding FAs be
a
a,b
a
r3+
a
b
FA1  p1±
p2
FA2  r1±
b
a,b
b
r2
As discussed earlier, the FA corresponding to the language (L1ČL2c)«(L1cČL2) helps in this regard i.e. if this
FA accepts any word then L1 and L2 are not equivalent other wise L1 and L2 are equivalent.
a
Following are the FAs corresponding to L1c and L2c
a,b
a
s3
a
FA2c
b
FA1c
q1-
s1-
q2+
b
a,b
b
s2+
FAs corresponding to (FA1c « FA2)c and (FA2c « FA1)c may be as follows
a
a
(FA2c«FA1)c
(FA1c«FA2)c
q1 , r3
p1 , s3
a
a
q1 , r1
-
-
b
b
a,b
a,b
p1 , s1
b
b
q2 , r2
p2 , s2
Both the FAs have no final state, so these FAs accept nothing. This implies that their union will not also accept
c
any string. Hence FA corresponding to the language (L1ČL2 )«(L1cČL2) accepts nothing. Thus both the
languages are equivalent.
Example
Following is an FA, for which it is required to decide whether it accepts any string or not? Using steps discussed
in method 2, the following FA can be checked whether it accepts any word or not.
88
img
Theory of Automata
(CS402)
1-
b
b
b
a,b
a
a
2
3
a
b
b
4+
a
5
6
a
1-
b
b
b
a
a,b
a
2
3
a
b
b
a
4+
5
6
a
1-
b
b
a,b
a
2
3
a
b
b
4+
a
6
5
a
1-
b
a,b
a
2
3
a
b
b
a
4+
5
6
89
img
Theory of Automata
(CS402)
1-
b
a
2
3
a
b
b
a
4+
5
6
As no final state of the FA is marked, so the given FA accepts no word.
Method 3
If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will
accept no word.
Note: It is to be noted that all the methods discussed above, to determine whether an FA accepts certain word,
are effective procedures.
Example: To determine whether the following FA accepts certain word, using method 3, all the strings of length
less than 4 (i.e. less than the number of states of the FA) are sufficient to be tested
2
a
a
a
a
b
1-
4+
b
b
3
b
i.e. Y, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb are required to be tested.
It can be observed that the strings aa, baa, aaa are accepted by this FA, hence the language accepted by this FA
is not empty.
Example
Consider the following FA. To determine whether this FA accepts some word, all the strings of length less than
4 (i.e. less than the number of states of this FA) are to be tested
a,b
a
b
a,b
b
4+
2
3
1-
a
It can be observed that none of the strings L, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, is
accepted by this FA. Thus the given FA cannot accept any word.
Observation
To find whether a regular expression defines an infinite language or not? The following possibilities are
required to be checked.
If a regular expression contains * then it may define an infinite language, with the exception Y* as Y* = Y e.g.
(Y+aY*)(Y*+Y)* defines finite language. While (Y*+aY*)* (Y*+Y)* defines an infinite language.
90
img
Theory of Automata
(CS402)
There are so many ways to decide whether an FA accepts a finite language or an infinite. Following is a theorem
in this regard
Theorem
Let F be an FA having N states
If F accepts a word w s.t. N length(w) < 2N
then F accepts infinite language.
If F accepts an infinite language then there are some words w s.t. N length(w) < 2N
The first part can be proved, using the pumping lemma version II.
Remark
There is an effective procedure to decide whether an FA accepts finite or infinite language. For a machine with
N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is mN +mN+1
+ mN+2 +... +m2N-1. After testing all these strings on the machine, if any is accepted then the machine accepts
infinite language other wise not. e.g. for machine of three states and alphabet of two letters, 2 3 +2 4 +2 5 = 56
strings are to be tested.
91
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