Theory of Automata

Content:

• Concatenation
• Palindrome
• Kleene Closure
• Lexicographical order
• Theorem 
• Positive Closure
• Examples

Concatenation: 

    Two strings are written down side by side to form a new longer string.

aaa concatenated with aa is the word aaaaa

an concatenated with am is the word an+m

For convenience, we may label a string in a given language by a new symbol. 

For example,

w = a1a2a3  and  v = b1b2 

              then

w v = a1a2a3b1b2

It is not true that when two strings are concatenated, they produce another string. 

For example, 

if the language is

L2 = {a, aaa, aaaaa, …} = {a2n+1 for n = 0, 1, 2, …}

then

w = aaa and v = aaaaa are both string

w  L2 v  L2

  but their concatenation w v = aaaaaaaa is not in L2

Note that in this simple example, we have: 

ab = ba

But in general, this relationship does NOT hold for all languages (e.g., houseboat and boathouse are two different words in English).

Example: Consider another language by beginning with the alphabet

∑ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Define the language

L3 = { any finite string of alphabet letters that does not start with the letter zero }

This language L3 looks like the set of positive integers:

L3 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, … }

If we want to define L3 so that it includes the string (word) 0, we could say

L3 = { any finite string of alphabet letters that, if it starts with a 0, has no more letters after the first}

Definition: Length

Length of a string to be the number of letters in the string.

Example:

• If a = xxxx in the language L1, then length(a) = 4
• If c = 428 in the language L3, then length(c) = 3
• If d = 0 in the language L3, then length(d)  = 1

In any language that includes the null word Λ, then length(Λ) = 0

For any word w in any language, if length(w) = 0 then w = Λ.

Recall that the language L1 does not contain the null string Λ. Let us define a language like L1 but that does contain Λ:

L4 = { Λ, x, xx, xxx, xxxx, … } 

           = { xn for n = 0, 1, 2, 3, … }

Here we have defined that

x0 = Λ (NOT x0 = 1 as in algebra)

In this way, xn always means the string of n alphabet letters x’s.

Remember that even Λ is a word in the language, it is not a letter in the alphabet. 

Definition: Reverse

If a is a string in some language L, then reverse(a) is the same string of letters/alphabets spelled in reverse order, even if this backward string is not a word in L.

Example:

reverse(aab) = baa

reverse(145) = 541

Note that 140 is a word in L3, 

but reverse(140) = 041 is NOT a word in L3

Definition: Palindrome

Let us define a new language called Palindrome over the alphabet

∑ = { a, b }

PALINDROME = { Λ, and all strings x such that     reverse(x) = x }

If we want to list the elements in PALINDROME, we find

PALINDROME = { Λ, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, abba, … }

Sometimes two strings/words in PALINDROME when concatenated will produce a word in PALINDROME

abba concatenated with abbaabba gives abbaabbaabba (in PALINDROME)

But more often, the concatenation is not a word in PALINDROME

aa concatenated with aba gives aaaba (NOT in PALINDROME)

The language PALINDROME has interesting properties that we shall examine later.

Kleene Closure

Definition: Given an alphabet ∑, we define a language in which any string of letters from ∑ is a word, even the null string Λ. We call this language the closure of the alphabet ∑, and denote this language by ∑*.

Examples:

If ∑ = { x } then ∑* = { Λ, x, xx, xxx, … } 

If ∑ = { 0, 1 } then ∑* = { Λ, 0, 1, 00, 01, 10, 11,       000, 001, … } 

If ∑ = { a, b, c } then ∑* = { Λ, a, b, c, aa, ab, ac,     ba, bb, bc, ca, cb, cc, aaa, … }

Lexicographic order

lexicographic order :

List words / string in a language according to size (i.e., words of shortest length first), and then list all the words of the same length alphabetically.

The star in the closure notation is known as the Kleene star.

Kleene star is an operation that makes, out of an alphabet, an infinite language (i.e., infinitely many strings, each of finite length).

Let us now generalize the use of the Kleene star operator to sets of words, not just sets of alphabet .

Definition: If S is a set of words, then S* is the set of all finite strings formed by concatenating words from S, where any word may be used as often as we like, and where the null string Λ is also included.

Example: If     S = { aa, b } 

   then

S* = { Λ + any word composed of factors of  aa and b }, or

S* = { Λ + any strings of a’s and b’s in which the a’s occur in even clumps }, 

or

S* = { Λ, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, aaaab, aabaa, aabbb, baaaa, baabb, bbaab, bbbaa, bbbbb, … }

Note that the string aabaaab is not in S* because it has a clump of a’s of length 3. 

Example:    Let S = { a, ab }

then

S* = { Λ + any word composed of factors of a and ab }, or

S* = { Λ, a, aa, ab, aaa, aab, aba, aaaa, aaab, abaa, abab, aaaaa, aaaab, aaaba, aabaa, aabab, abaaa, abaab, ababa, … }

Note that for each word in S*, every b must have an a immediately to its left, so the double b, that is bb, is not possible; neither any string starting with b.

How to prove a certain word is in the closure language S*

In the previous example, to show that abaab is in S*, we can factor it as follows:

abaab = (ab)(a)(ab)

If ab  S

a  S

then            

abaab  S*

Note that the parentheses, ( ), are used for the sole purpose of demarcating the ends of factors.

if          ∑ = ø (the empty set), 

        then

∑* = { Λ }

Also, observe that if the set S has the null string as its only word, then the closure language S* also has the null string as its only word; that is

if S = { Λ }, then S* = { Λ }

     because ΛΛ = Λ.

Hence, the Kleene closure always produces an infinite language unless the underlying set is one of the two cases above.

Kleene Closure of different sets

The Kleene closure of two different sets can end up being the same language.

Example:

Consider two sets of words

S = { a , b, ab } and T = { a, b, bb }

Then, both S* and T* are languages of all strings of a’s and b’s since any string of a’s and b’s can be factored into syllables of (a) or (b), both of which are in S and T.

Positive Closure:

Positive Closure: Include all set of strings from alphabet ∑  except null string.

  Denoted by ∑ +.  This “plus operation” is called positive closure.

Example: 

if ∑ = { x }   then ∑+ = { x, xx, xxx, … } 

Observe that

S* - Λ = S+ 

                 Similarly  ∑* - Λ = ∑+  

Or reverse

∑+ + Λ = ∑*

 

S**?

What happens if we apply the closure operator twice?

We start with a set of words S and form its closure S*

We then start with the set S* and try to form its closure, which we denote as (S*)* or S**

Theorem 1:

For any set S of strings, we have S* = S**

Before we prove the theorem, recall from Set Theory that

A = B if A is a subset of B and B is a subset of A

A is a subset of B if for all x in A, x is also in B

Proof of Theorem 1:

Let us first prove that S** is a subset of S*:

let  w is string   and w  S** 

    Then factors   of w  S*.

Every factor let  v  S*   and factors of v  S. 

  

   Hence, every string from S** is made up of factors from S.     

    

   Therefore, every word in S** is also a word in S*. 

  =>             S** is a subset of S*.

Let us now prove that S* is a subset of S**:

In general, it is true that for any set A, we have A is a subset of A*, because in A* we can choose as a word any factor from A. So if we consider A to be our set S* then 

=>         S* is a subset of S**

From two inclusions, prove that 

     S* = S**

Example

Defining language of EVEN

Step 1:

      2 is in EVEN.

Step 2:

If x is in EVEN then x+2 and x-2 are also in EVEN. 

Step 3:

No strings except those constructed in above, are allowed to be in EVEN.

Defining the language factorial

Step 1:

As 0!=1, so 1 is in factorial.

Step 2:

n!=n*(n-1)! is in factorial.

Step 3:

No strings except those constructed in above, are allowed to be in factorial.

Defining the language PALINDROME, defined over Σ = {a,b} 

Step 1:

a and b are in PALINDROME

Step 2:

if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to Σ*

Step 3:

No strings except those constructed in above, are allowed to be in palindrome

Defining the language {anbn }, n=1,2,3,… , of strings defined over Σ={a,b}

Step 1:

ab  {anbn} 

Step 2:

if x is in {anbn}, then axb is in {anbn} 

Step 3:

No strings except those constructed in above, are allowed to be in {anbn}

Defining the language L, of strings containing aa or bb , defined over       Σ={a, b}

Step 1:

aa and bb are in L 

Step 2:

s(aa)s and s(bb)s are also in L, where s  Σ*

Step 3:

No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings containing exactly aa, defined over    Σ={a, b}

Step 1:

aa  L 

Step 2:

  s(aa)s is also in L, where s  b*

Step 3:

No strings except those constructed in above, are allowed to be in L