Three basic concepts
Languages, Grammers, Automata
Languages
To understand languages, we need to look at a few things.
Symbol: think of consonants and vowels in Hangul, or the digits 0~9 in decimal. The most basic element that makes up a language.
Alphabet: you should think of the English alphabet as one kind of alphabet. It's a finite set of one or more symbols (not the empty set). Usually written as Σ.
String: a finite-length sequence of symbols belonging to an alphabet. Built from individual symbols.
ex) if alphabet is Σ = {a, b}, abab or aaabba is String about alphabet Σ
Concatenation of strings: the string obtained by attaching string v to the right of string w
w = a1a2...an
v = b1b2...bn
Concatenation wv = a1a2...anb1b2...bn
Reverse string: the string in reverse order
Length: the length of string w is written ∣w∣. ∣uv∣ = ∣u∣ + ∣v∣ holds.
Empty string: written λ, ∣λ∣ = 0. ∣λ∣w = w∣λ∣ = w
Substring: a string of consecutive characters that exist within string w.
Prefix : when w = vu, it refers to v.
Suffix : when w = vu, it refers to u.
For w = abbab,
{λ, a, ab, abb, abba, abbab} is the set of all prefixes of v.
{abbab, bbab, bab, ab, b} is the set of all suffixes of u.
Σ* = for an alphabet Σ, the set of all strings obtained by concatenating zero or more symbols in Σ (of course λ is included too)
Σ+ = the set Σ* excluding λ, Σ* - λ = Σ+
Σ is a finite set, but Σ* and Σ+ are infinite sets because there's no limit on string length.
Now let's understand languages.
Language: in general, a subset of Σ*.
Sentence: a string belonging to some language L is called a sentence of language L.
Any set of strings over a given alphabet Σ can be considered a language, so it's very broad.
Let's understand languages more through examples.
If Σ = {a, b}, then Σ* = {λ, a, b, aa, ab, ba, bb, aab, ...............}.
Since a language is a subset of Σ*, {a, b, aa, ab} is a language over Σ.
Since this set has a finite number of elements, it's called a finite language.
This time let the set L be L = { anbn: n >= 0 }.
Since this set has infinitely many strings, it's called an infinite language
Since languages are sets too, set operations (union, intersection, difference) are defined.
Complement of a language: the complement is defined with respect to Σ*. That is, Lc = Σ* - L.
Reverse of a language: the set of reverse strings of all strings belonging to a language. LR = { wR : w ∈ L }
Concatenation of languages: the concatenation of languages L1 and L2 is the set of all strings obtainable by concatenating elements of the two languages.
L1L2 = { xy: x ∈ L1, y ∈ L2 }.
The language made by concatenating language L n times = Ln
Star-closure: L* = L0 ∪ L1 ∪ L2 ∪ ...
Positive-closure: L+ = L1 ∪ L2 ∪ ...
Example)
Let language L be L = { anbn: n >= 0 }.
We said the language made by concatenating L twice is L2.
So L2 = { anbnambm: n >= 0, m >= 0 },
and LR = { bnan: n >= 0 }.
Languages Lc and L* have the limitation that they're hard to express as sets.
Grammers
To study languages mathematically, we need to be able to describe them.
But everyday languages are imprecise, ambiguous, and informal.
We saw that languages can be expressed in set notation, but that has limitations.
So we'll study techniques for defining languages, and among them we study grammars, the most powerful technique.
A grammar G is defined as a quadruple.
G = (V, T, S, P), where V and T are nonempty and disjoint.
V : a finite set of objects called variables
T : a finite set of objects called terminal symbols
S : a special symbol in V, called the start variable
P : a finite set of productions
Looking at productions first,
every production has the form x → y.
Here, x ∈ ( V ∪ T )+, y ∈ ( V ∪ T )*
If we define string w as w = uxv,
the production x → y can be applied to this string, and by using the production to replace x with y
we can get the string z = xyv.
This is written w ⇒ z, and we say 'w derives z' or 'z is derived from w'.
Derivations can happen in succession, and when a ⇒ b ⇒ c ⇒ d ⇒ ... ⇒ z
we write a ⇒* z. (see picture)
The * means that when z is derived from a, there may be an unspecified number of steps. (or there may not be)
By applying productions in different orders, a grammar can generate many strings.
The set of all such terminal strings is called the language generated, or defined, by the given grammar.
Now, given a grammar G = (V, T, S, P), the language L(G) is defined as follows:
L(G) = { w ∈ T*: S ⇒* w }
Derivation : if w ∈ L(G), then S ⇒ w1 ⇒ w2 ⇒ ... ⇒ w is called a derivation of sentence w.
Sentential form : S, w1, w2, ... , w of the derivation are called the sentential forms in this derivation.
Example)
Let grammar G = ( {S}, {a, b}, S, P = {S → aSb, S → λ} ).
A derivation like S ⇒ aSb ⇒ aaSbb ⇒ aabb is possible.
This can be written S ⇒* aabb.
aabb ∈ L(G), and aaSbb is a sentential form.
It can be hard to express L(G) as the set of strings itself,
but by guessing we can write L(G) = { anbn: n >= 0 }.
Automata
An abstract model of a digital computer.
Assumes it operates in discrete time units.
Divided into deterministic automata and nondeterministic automata.
If each automaton's subsequent behavior can be uniquely determined, it's a deterministic automaton,
and if several moves are possible so that the set of subsequent behaviors can be predicted, it's a nondeterministic automaton.
If the automaton's output is simply 'YES' or 'NO', it's called an accepter.
More generally than an accepter, if it can output arbitrary strings, it's called a transducer.
Essential features :
Input file
-
A string over the given alphabet is input cell by cell
-
The automaton can read it but cannot change it.
-
Each cell can store one symbol.
-
Reads one symbol at a time from left to right.
-
Can recognize the end of the string by detecting the end-of-file condition.
Storage
- Made up of infinitely many cells, each cell stores one symbol from the given alphabet.
Control unit
- Can be in one of a finite number of internal states, and can change state according to predefined rules.
