Theory of Automata and Computational Theory
Introduction to Language
Alphabet
A finite, nonempty set of symbols.
Symbol: Σ
Examples:
The binary alphabet: Σ = {0, 1}
The set of all lower-case letters: Σ = {a, b, . . . , z}
The set of all ASCII characters
Strings
A string (or sometimes a word) is a finite sequence of symbols chosen
from some alphabet.
Example: 01101 and 111 are strings from the binary alphabet Σ = {0,
1}
This string is denoted by ε.
Length of a string: the number of positions for symbols in the string.
Example: 01101 has length 5
There are only two symbols (0 and 1) in the string 01101, but 5
positions for symbols
Notation of length of w: |w| Example: |011| = 3 and | ε | = 0
Power of Alphabet
If Σ is an alphabet, we can express the set of all strings of a certain
length from that alphabet by using the exponential notation:
Σ k: the set of strings of length k, each of whose is in Σ.
Examples:
Σ 0 : {ε}, regardless of what alphabet Σ is. That is ε is the only string of length 0
If Σ = { 0, 1 }, then:
- Σ 1 = { 0, 1 }
- Σ 2 = {00, 01, 10, 11 }
- Σ 3 = {000, 001, 010, 011, 100, 101, 110, 111 }
Note: confusion between Σ and Σ 1 :
- Σ is an alphabet; its members 0 and 1 are symbols
- Σ 1 is a set of strings; its members are strings (each one of length 1)
Kleene star
Σ∗: The set of all strings over an alphabet Σ
{0, 1}∗ = {ε, 0, 1, 00, 01, 10, 11, 000, . . .}
Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ . . .
The symbol ∗ is called Kleene star and is named after the
mathematician and logician Stephen Cole Kleene.
Languages
If Σ is an alphabet, and L ⊆ Σ∗, then L is a (formal) language over Σ.
Language: A (possibly infinite) set of strings all of which are chosen
from some Σ∗
A language over Σ need not include strings with all symbols of Σ
Thus, a language over Σ is also a language over any alphabet that is a
superset of Σ
Examples:
Programming language C
Legal programs are a subset of the possible strings that can be
formed from the alphabet of the language (a subset of ASCII
characters)
English or French
Other Languages
The language of all strings consisting of n 0s followed by n 1s ( n ≥
0):
{ε, 01, 0011, 000111, . . . }
- The set of strings of 0s and 1s with an equal number of each:
{ε, 01, 10, 0011, 0101, 1001, . . . }
Important operators in Language
Union
Concatenation
Union
The union of two languages L and M, denoted L ∪ M, is the set of
strings that are in either L, or M, or both.
Example
If L = {001, 10, 111 } and M = {ε, 001 }
then L ∪ M = {ǫ, 001, 10, 111 }
Concatenation
The concatenation of languages L and M, denoted L.M or just LM , is
the set of strings that can be formed by taking any string in L and
concatenating it with any string in M.
Example If L = {001, 10, 111 } and M = {ε, 001 }
then L.M = {001, 10, 111, 001001, 10001, 111001 }
The closure of a language L is denoted L ∗ and represents the set of
those strings that can be formed by taking any number of strings
from L, possibly with repetitions (i.e., the same string may be selected
more than once) and concatenating all of them.
Examples:
If L = { 0, 1 } then L ∗ is all strings of 0 and 1
If L = { 0, 11 } then L ∗ consists of strings of 0 and 1 such that the 1
come in pairs, e.g., 011, 11110 and ε. But not 01011 or 101.
Formal Language
A formal language consists of words whose letters are taken from
an alphabet and are well-formed according to a specific set of rules.
Language
Theoretically, there are infinitely many different words in the
language ENGLISH-SENTENCES.
For example, I ate one apple. I ate two apples. 1 ate three apples.
The trick of defining the language ENGLISH-SENTENCES by listing all
the rules of English grammar al lows us to give a finite description of
an infinite language.
Grammar
The set of rules defining English is a grammar in a very precise sense.
We shall take a much more liberal view about what kinds of “sets of
rules” define languages.
Defining Language
L = { any finite string of alphabet letters that, if it starts with a 0, has
no more letters after the first }