10. When are two finite acceptors M 1 and M 2 said to be equivalent?
Two finite acceptors M 1 and M 2 are said to be equivalent if
L M
L M
( )
(
)
1
2
=
i.e., if both accept the same language.
11. Is it possible to convert every NFA into an equivalent DFA?
Yes, it is possible to convert every NFA into an equivalent DFA and
vice-versa.
12. What are regular languages?
Regular languages are those languages that can be constructed from
the three set operations (a) Union (b) Concatenation and (c) Kleene star.
13. Give the formal definition of a regular language.
Let Σ be an alphabet. The class of ‘regular languages’ over Σ is
defined inductively as follows:
(a) ∅ is a reg u lar lan guage
(b) For each σ
σ
∈ Σ, { } is a regular language
(c) For any natural number n ≥ 2 if L L
L n
1
2
, , KK
are regular
languages, then so is L
L
L n
1
2
∪
∪
KK
.
(d) For any natural number n ≥ 2 if L L
L n
1
2
, , KK
are regular
languages, then so is L L
L n
1
2
o o KK o .
(e) If L is a regular language, then so is L
* .
(f) Nothing else is a regular language unless its construction
follows from rules (a) to (e).
14. Give an example of a regular language.
The language over the alphabet {0, 1} whose strings contain an even
number of 0’s can be constructed by
1*((01
* )(01
* ))
* )
or simply 1
* (01
* 01
* )
* .
15. What is the motivation behind writing regular expressions?
Regular expresions were designed to represent regular languages
with a mathematical tool, a tool built from a set of primitives and
operations.
16. How are regular expressions formed?
A regular expression is obtained from the symbols {a, b, c}, empty
string ∈, and empty set ∅ performing the operations +, ⋅ and * (union
concatenation and Kleene star).
17. What do the following regular expressions represent?
(a) (0 + 1) 1 (b) (
) (
)
a b b c
+ ⋅ +
(c) (0 + 1)
* (d) 0 (e) (0 + 1)
+
(a) (0 + 1) 1 rep re sents the set {01, 11}
(b) (
) (
)
a b b c
+ ⋅ + represents the set {ab, bb, ac, bc}
110
Theory of Automata, Formal Languages and Computation