ZeePedia

Decidability

<< Pseudo theorem
finiteness of a language >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 29
Reading Material
Introduction to Computer Theory
Chapter 10, 11
Summary
Example of prefixes of a language, Theorem: pref(Q in R) is regular, proof, example, Decidablity, deciding
whether two languages are regular or not ?, method 1, example, method 2, example
Example
Let Q and R be expressed by ab*a and (ba)* respectively i.e. Q={aa,aba,abba, ...} and
R={Y, ba, baba, bababa, ...}. aba is the only word in Q which can make a word in R, because the words in R
don't contain the double letter. Thus pref(Q in R) = {b, bab, babab, ...}, which can be expressed by b(ab)* or
(ba)*b.
Remark
It may be noted that the language R cannot be factorized with the help of language Pref(Q in R) i.e.
Pref(Q in R)Q is not equal to R in general. However the following theorem shows that the language pref(Q in R)
is regular if R is regular, no matter whether the language Q is regular or not.
Theorem
Statement
If R is regular language and Q is any language (regular/ nonregular), then Pref(Q in R) is regular.
Proof
Since R is regular there exists an FA that accepts this language. Choose a state, say, s of this FA and see whether
this state can trace out a path ending up in a final state while running words from Q. If this state traces out a path
ending up in a final state for any of the words of Q, mark this state with certain colour.
Repeat this process for remaining states of the machine. If at least one state of this machine is marked then it can
be shown that the language Pref(Q in R) is non-empty. Now build a new FA with some marked states by
considering the initial state that of original FA and final states which are marked. The machine, thus obtained
accepts exactly the language Pref(Q in R). Thus Pref(Q in R) being accepted by an FA is regular.
Remark
There is a problem in deciding whether a state of FA should be marked or not when the language Q is infinite.
This proof just gives non constructive method to prove that Pref(Q in R) is regular.
Example
Consider the languages Q={aba, abb} and R = {w OE {a,b}*: length(w) ≥ 2, w ends in either ab or ba}, where R
may be accepted by the following FA
a
b
4+
2
a
b
a
1­
a
b
b
b
a
5+
3
It can be observed that the string aba from Q make the words of R and hence the states 1,2,3,4 and 5 can easily
be marked. Thus from the given FA, making the states 1, 2 and 3 to be final as well, the resulting FA will accept
the language pref(Q in R). Moreover it can be observed that pref(Q in R) can be expressed by (a+b)*, which is
the RE corresponding to the resulting FA as well.
Decidability
Effectively solvable problem
84
img
Theory of Automata
(CS402)
A problem is said to be effectively solvable if there exists an algorithm that provides the solution in finite
number of steps e.g. finding solution for quadratic equation is effectively solvable problem, because the
quadratic formula provides an algorithm that determines the solution in a finite number of arithmetic operations,
(four multiplications, two subtractions, one square root and one division).
Decision procedure
If an effectively solvable problem has answer in yes or no, then this solution is called
decision procedure.
Decidable problem
A problem that has decision procedure is called decidable problem e.g. the following problems
The two regular expressions define the same language.
The two FAs are equivalent.
Determining whether the two languages are equivalent or not ?
If L1 and L2 are two regular languages, then they can be expressed by FAs. As shown earlier, L1c , L2c , L1Č L2 ,
L1« L2 are regular languages and the methods have already been developed to build their corresponding FAs. It
can be observed that (L1Č L2c ) « ( L1c Č L2 ) is regular language that accepts the words which are in L1 but not
in L2 or else in L2 but not in L1 . The corresponding FA cannot accept any word which is in both L1 and L2 i.e. if
L1 and L2 are equivalent, then this FA accepts not even null string. Following are the methods that determine
whether a given FA accepts any words
Method 1
For FA corresponding to (L1ČL2c ) « ( L1cČ L2 ), the regular expression can be determined that defines the
language accepted by this FA. From that regular expression one can determine whether this regular expression
defines any word or not? Following are the steps to be followed
Remove all *s from the regular expression.
Separate the right part of + and the plus itself.
The regular expression thus obtained if contains atleast one word then the language is not empty otherwise the
language is empty.
Example
For (a+Y)(a*b+ba*)(a*+Y)* to be the regular expression of (L1ČL2c ) « ( L1cČ L2 ), it is required to find
whether this language accepts any string or not?
After removing all *s the RE will be (a+Y)(ab+ba)(a+Y)
After separating the right part from + and the + itself the RE will be aaba
As this language contains atleast aaba as its word, so this language is not empty.
Remark
Sometimes, while determining regular expression for a given FA, it is impossible to write its regular expression
a
b
e.g.
a
FA1
2
1-
b
a,b
a,b
FA2
1-
2
a,b
a,b
a,b
3+
FA3
2
1-
Method 2
To examine whether a certain FA accepts any words, it is required to seek the paths from initial to final state.
But in large FA with thousnads of states and millions of directed edges, without an effective procedure it is
impossible to find a path from initial to final state. Following are the steps of this procedure
85
img
Theory of Automata
(CS402)
Mark the initial state.
For every marked state follow each edge that leads out of it and marked the concatenating states and delete these
edges.
Repeat step 2 until no new state is marked.
If any of the final states are marked then the FA accepts some word, otherwise not.
Example
Suppose it is required to test the FA, which is given below, whether it accepts any string or not? Applying
method 2 as
b
a
a
a
b
b
6+
4
5
3
a
b
a,b
a
b
1-
2
b
a
a
a
b
b
6+
4
3
5
a
b
a
a,b
b
1-
2
b
a
a
a
b
b
4
5
6+
3
a
b
a,b
1-
2
b
a
a
b
a
b
6+
3
4
5
a
b
b
a
a
b
4
6+
5
3
a
b
2
1-
1-
2
86
img
Theory of Automata
(CS402)
b
a
b
6+
4
5
3
a
1-
2
This FA accepts no string as after applying method 2, the final state is not marked.
87
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