Xem mẫu
- Lecture # 2
Theory Of Automata
By
Dr. MM Alam
- Lecture#1 Recap
•
Definition of the word Automata
•
Types of languages, empty/Null String,
Alphabets, words, length of strings,
Palindromes
•
How to form palindromes of even and odd
length.
- Question
•
Q) Prove that there are as many palindromes
of length 2n, defined over Σ = {a,b,c}, as
there are of length 2n-1, n = 1,2,3… .
Determine the number of palindromes of
length 2n defined over the same alphabet as
well.
•
Example:- L={aa,ab,ac,bb,ba,bc,cc,ca,cb} = 9
words.
- Solution
•
Since the number of symbols are 3 in the
alphabet, therefore, the length of 2n
palindromes will be 3n. As 2n means that
palindromes are of even length.
- Solution (Cont’d)
Similarly, for palindromes of length 2n-1,
we need to calculate their number for each
respective symbol in the alphabet, that is,
the required number of palindromes are 3n-
1 for symbol a
Similarly the number of palindromes of
length 2n-1, with b or c as middle letter,
will be 3n-1 as well. Hence the total number
of palindromes of length 2n-1 will be :
3n-1 + 3n-1 + 3n-1 = 3 (3n-1)= 3n .
- Consider the language of Palindrome over
the alphabet {a,b}. Prove that if x is in
PALINDROME then so is xn for any n.
Example: suppose x = aba and is a palindrome
and xr = (aba)r = aba
Then: (aba)5 = (aba aba aba aba aba aba)r
=aba aba aba aba aba
which is again a palindrome
- Proof. It is true for n = 0 by assumption xn is
palindrome.
Assume that it is true for n-1 namely xn-1 is
in palindrome and (xn-1)r = xn-1. Now as
we know that (xy)r = yrxr .
(xn )r = (xn-1x)r = xr (xn-1)r = x xn-1 =
xn. Thus, xn is in palindrome
- Kleene Star closure
•
In order to further generalize the notation
of any combination of strings the famous
logician kleene and founder of the ‘Theory
of Automata’ subject has introduced a
notation called kleene closure.
•
It is denoted by Σ*and represent all
collection of strings defined over Σ
including Null string.
- •
The language produced by Kleene closure
is infinite. It contains infinite words,
however each word has finite length.
- Examples
•
If Σ = {x}
Then Σ* = {Λ, x, xx, xxx, xxxx, ….}
•
If Σ = {0,1}
Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….}
•
If Σ = {aaB, c}
Then Σ* = {Λ ,aaB, c, aaBaaB, aaBc, caaB,
cc, ….}
- Q) Consider the language S*, where S = {a b}.
How many words does this language have of
length 2? of length 3? of length n?
A) Number of words = nm
Length 2: 22 = 4
Length 3: 23= 8
Length n: 2n
- •
Consider the language S*, where S = {aa
b}. How many words does this language
have of length 4? of length 5? of length 6?
What can be said in general?
Words of length 0: Λ = 1 word
Words of length 1: b = 1 word
Words of length 2: (Add aa to all words of
length 0 --> 0 + 2 = 2)
Add b to all words of length 1 --> 1 + 1 = 2)
- Words of length 3:
(Add aa to all words of length 1 --> 1 + 2 =
3)
(Add b to all words of length 2 --> 2 + 1 = 3)
aab baa bbb = 3 words
Words of length 4:
(Add b to all words of length 3)
(Add aa to all words of length 2)
baab bbaa bbbb aaaa aabb = 5 words
- Words of length 6:
(Add aa to the 5 words of length 4)
(Add b to the 8 words of length 5) = 13
words
This is the Fibonacci sequence:
1,2,3,5,8,13,…
- •
Consider the language S*, where S = {ab
ba}. Write out all the words in S* that have
seven or fewer letters. Can any word in
this language contain the substrings aaa
or bbb? What is the smallest word that is
not in this language?
Words of length 0: Λ
Words of length 2: ab ba
Words of length 4: abab abba baab baba
Words of length 6: ababab ababba abbaab
- •
No words can contain aaa or bbb because
the first a in string ab and the a in ba
never allow to make aaa or bbb.
- •
Consider the language S*, where S
= {xx xxx}. In how many ways can x
19 be written as the product of
words in S? This means: How many
different factorizations are there of x
19 into xx and xxx?
Example: (xx) (xx) (xx) (xx) (xx) (xx) (xx) (xx)
+ (xxx)
= x16+x3=x19
- Cont’d…
3 doubles can be replaced by 2 triples: (xx)
(xx)(xx) = (xxx)(xxx)
Let xx = d and xxx = t
•
The number of ways of factoring 19 x’s
into d’s and t’s is equal to:
•
The number of ways of arranging 8d’s and
1t
+ the number of ways of arranging 5 d’s and
3 t’s
- (i) Let S = {ab bb} and let T = {ab, bb, bbbb}.
Show that S* = T*.
(ii) Let S = {ab, bb} and let T = {ab, bb, bbb}.
Show that S* ≠ T*, but that S* ⊂ T*
(i) S* = {Λ and all possible concatenations of
ab and bb}
T* = {Λ and all possible concatenations of
ab, bb, and bbb}, but bbb is just bb
concatenated with itself, so
T* = {Λ and all concatenations of ab and bb}
- •
(ii) Let S = {ab, bb} and let T = {ab, bb,
bbb}. Show that S* ≠ T*, but that S* ⊂ T*
•
The reason is that T contains triple b, and
S contains double b. S* will always add
double b, thus resulting string will be even
only. However, S* ⊂ T*. Please evaluate
S* and T* to prove above statement.
nguon tai.lieu . vn
