An alphabet
is any set of finite symbols such as a
and b
. For example, the alphabet Σ = {a, b}
is an alphabet that contains the strings
that can be built by combining a
and b
and the alphabet Σ = {0, 1}
is the an alphabet that contains the strings that can be built by combining 0
and 1
.
Symbols such as a
and b
put together to form something like bbaa
are called strings
.
bbaa
is astring
built from thesymbols
a
andb
Alphabets and symbols can be used to create a language
which is a set of strings over some fixed alphabet.
Given the language L = x ∈ {0, 1}* | x starts_with(x, 10)
:
S -> 1A
A -> 10B
B -> 10B | 1B | 0B | ε
We can try to match a few strings:
10 (Matches)
S -> 1A
A -> 10B
B -> ε
01 (Doesn't match)
S -> No match
101 (Matches)
S -> 1A
A -> 10B
B -> 1B
B -> ε
ε
is the empty string and it is being used to stop the recursion.
Some of this comes from one of the books I’m reading at the moment: FORMAL LANGUAGE: A PRACTICAL INTRODUCTION