Basic definitions of Automaton

Idea

TODO

An Alphabet, ∑, is a non-empty set of symbols.

For example:

• ∑={0, 1} is a binary alphabet.
• ∑={a, b, c, d, …, z} is the collection of lower case letters.

A string or word is a finite sequence of letters drawn from an alphabet.

For example:

• x=01101100 is a binary string
• “Life is good” is also a string

Empty strings denoted by ϵ (epsilon) are strings with zero occurrences of letters. Empty strings can be from any alphabet.

Length of a string, x, is the sum of occurrences of its symbols, denoted by |x|.

For example:

• If x=01101100, then |x|=8
• The length of “Life is good” is 12

The set of all strings composed from letters in ∑ is denoted by ∑*.

For example: If ∑={0, 1} then ∑*={ϵ, 0, 1, 00, 01, 10, 11, 000, …}

The set of all non-empty strings composed from letters in ∑ is denoted by ∑⁺.

The set of all strings of length k composed from letters in ∑ is denoted by ∑ᵏ.

For example: If ∑={0, 1} then ∑²={00, 01, 10, 11}

Size of ∑ᵏ=|∑|ᵏ

A language is a collection of strings over an alphabet

For example: The language of palindromes over the binary alphabet is {ϵ, 0, 1, 00, 11, 010, 101, 000, …}

Is ∑ the same as ∑¹ ?

• No, because the elements in ∑ are called symbols and they are just letters, whereas the elements in ∑¹ are strings; they just happen to have length 1.
• Do not mix types in programming.