Xem mẫu
- Lecture # 3
Theory Of Automata
By
Dr. MM Alam
- Lecture#2 Recap
•
Kleene Closure
•
Examples of Kleene Closure.
•
Plus Operation
- Prove that for all sets S,
(i) (S+)* = (S*)*
(ii) (S+)+ = S+
(iii) Is (S*)+ = (S+)* for all sets S?
S+ = {all concatenations of words in S,
excluding Λ}.
(S+)* = {Λ and all concatenations of words in
S+}
- S* = {Λ and all concatenations of words in
S}
(S*)* = {Λ and all concatenations of words in
S}
= {Λ and all concatenations of (Λ and all
concatenations of words in S)}
= {Λ and all concatenations of words in S}
= S*
Therefore (S+)* = (S*)* = S*
- (ii) (S+)+ = S+
S+ = {all concatenations of words in S,
excluding Λ}
(S+)+ = {all concatenations of words in S+,
excluding Λ}
= {all concatenations of (all concatenations
of words in S, excluding Λ) excluding Λ)}
= {all concatenations of words in S,
excluding Λ}
= S+
- (iii) Is (S*)+ = (S+)* for all sets S?
S* = {Λ and all concatenations of words in
S}
(S*)+ = {all concatenations of words in S*,
but not Λ}
S* already contains Λ, so (S*)+ contains Λ
too, since it’s part of the language.
No new words are added with the +
operator, so (S*)+ = S*.
- S+ = {all concatenations of words in S,
without Λ}
(S+)* = {Λ and all concatenations of words in
S+}
= {Λ and all concatenations of (all
concatenations of words in S, not Λ)}
= {Λ and all concatenations of words in S}
= S*
The external * operator only added Λ to the
- Let S = {a, bb, bab, abaab}. Is abbabaabab in
S*? Is abaabbabbaab? Does any word in S* have
an odd total number of b’s?
(a)(bb)(abaab)ab can’t be factored into substrings
from S, so it is not in the language. (abaab)
(bab)b
(a)(a)(bb) can’t be factored into substrings from
S, so it’s not in the language.
It is not possible to have an odd no of b’s. The
reason is that even b’s +even b’s = even b’s
- Suppose that for some language L we can
always concatenate two words in L and get
another word in L if and only if the words are
not the same. That is, for any words w1 and w2
in L where w1 ≠ w2, the word w1w2 is in L but
the word w1w1 is not in L. Prove that this
cannot happen.
w1 ∈ L and w2 ∈ L (2 different words)
therefore (w1)(w2) ∈ L
w1w2 ∈ L and w1 ∈ L (2 different words)
- •
Let us define (S**)* = S*** Is this set
bigger than S*? Is it bigger than S?
•
S*** is no bigger than S*. Both sets
contain an infinite number of elements.
S*** is bigger than S (if S is not {Λ})
because it is made up of all
concatenations of elements in S.
- •
(i) If S = {a b} and T* = S*, prove that T
must contain S. (ii) Find another pair of
sets S and T such that if T* = S*, then S ⊂
T
(i)
S* = {Λ and all concatenations of a’s and
b’s} = T*.
This means that a ∈ T and b ∈ T. (The
smallest words in S* and T*).
T may contain other strings (only
- (ii) Find another pair of sets S and T such
that if T* = S*, then S ⊂ T
T = {a, b, aa, abb}
S⊂T
S = {a b aa}
•
Still S* = T* but S ⊂ T
- Four different ways, in which a
language can be defined
•
So far, we have studied many languages
like INTEGER, PRIME, PALINDROME etc.,
•
Now, we will take a detailed look at how a
language can be defined in different ways.
•
There are four ways that we will study in
this course:
– Descriptive way
– Recursive way
– Regular Expression
- Descriptive Definition of a
Language
•
The language and its associated conditions
are defined in plain English.
•
This way is semi-formal way with chances of
ambiguity.
•
Descriptive method is used in early phases of
requirement engineering and resultant
equations are then formally transformed using
other methods.
- •
Example:
The language L of strings of even length,
defined over Σ={b}, can be written as
L={bb, bbbb, …..}
•
Example:
The language L of strings that does not
start with a, defined over Σ={a,b,c}, can be
written as
L={b, c, ba, bb, bc, ca, cb, cc, …}
- •
Example:
The language L of strings of length 3,
defined over Σ={0,1,2}, can be written as
L={000, 012, 022,101, 101,120,…}
•
Example:
The language L of strings ending in 1,
defined over Σ ={0,1}, can be written as
L={1,001,101,0001,0101,1001,1101,…}
- •
Example: The language EQUAL, of
strings with number of a’s equal to number
of b’s, defined over Σ={a,b}, can be written
as
{Λ ,ab,aabb,abab,baba,abba,…}
•
Example: The language EVEN-EVEN, of
strings with even number of a’s and even
number of b’s, defined over Σ={a,b}, can
be written as
{Λ, aa, bb, aaaa,aabb,abab, abba, baab,
- •
Example: The language INTEGER, of
strings defined over
Σ={-,0,1,2,3,4,5,6,7,8,9}, can be written as
INTEGER = {…,-2,-1,0,1,2,…}
•
Example: The language EVEN, of stings
defined over Σ={-,0,1,2,3,4,5,6,7,8,9}, can be
written as
EVEN = { …,-4,-2,0,2,4,…}
- •
Example: The language {anbn }, of strings
defined over Σ={a,b}, as
{an bn : n=1,2,3,…}, can be written as
{ab, aabb, aaabbb,aaaabbbb,…}
•
Example: The language {anbncn }, of
strings defined over Σ={a,b,c}, as
{an bn cn: n=1,2,3,…}, can be written as
{abc, aabbcc, aaabbbccc,aaaabbbbcccc,
- Lecture#3 Summary
•
Plus Operation Examples
•
Four ways of defining languages
•
Examples for Descriptive way of defining
languages
nguon tai.lieu . vn
