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.
bbaais astringbuilt from thesymbolsaandb
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