1.3.1. Alphabet, grammar and Language¶

1.3.1.1. Alphabet¶

In Language Theory an alphabet is a set of indivisible symbols, characters or glyphs, used to construct strings. Strings are known as words or sentenses over an alphabet as a sequence of symbols from the alphabet

1.3.1.1.1. Mathematical formalization¶

Let \(\Sigma = \{a_1,\ a_2,...,\ a_n\}\) where \(\Sigma\) is the alphabet, and each \(a_i\) is a symbol from the alphabet. The set \(\Sigma^*\) represents the sets of strings that can be formed from the alphabet \(\Sigma\) including \(\varepsilon\) as the empty string.

1.3.1.1.2. Alphabet examples¶

roman alphabet: \(\Sigma = \{a,b,c,d,e,f,...,x,y,z\}\)

an alphabet with words: \(\Sigma = \{dog, cat, bird\}\)

binary alphabet: \(\Sigma = \{0,1\}\)

1.3.1.2. Terminals and Non-terminals¶

Terminals are symbols form the alphabet that appear in the final string of the language. They are the basic building blocks of the language.

Non-terminals are symbols used to form production rules in a grammar but do not appear in the final strings. They are intermediate symbols and they are used to generate other terminal or non-terminal symbols.

1.3.1.2.1. Mathematical formalization¶

Let \(T\) be the set of terminals, \(N\) be the set of non-terminals and \(S\) a start symbol where \(S \in N\).

1.3.1.2.2. Terminals and Non-terminals examples¶

Classical example

\(T =\{a,\ b\}\)

\(N =\{S\}\)

Rule:

\(S \to aSb \mid \varepsilon\)

With words

A given alphabet: \(\Sigma = \{hello, goodbye\}\)

Two given non-terminals: \(N = \{S,\ A\}\)

Rules:

\(S \to hello\ A\)

\(A \to goodbye\)

Result: hello goodbye

1.3.1.3. Grammar¶

A formal grammar is a set of production rules that define a formal language. Each rule replaces a non-terminal symbol with sequence of terminal and non-terminal symbols.

1.3.1.3.1. Mathematical formalization¶

A grammar \(G\) is a quadruple \(G = (N,\ T,\ P,\ S)\)

where :

\(N\) is a set of non-terminals

\(T\) is a set of terminals

\(P\) is a set of production rules \((A \to \alpha)\)

\(S \in N\) is the start symbol

1.3.1.3.2. Grammar example¶

Consider the grammar \(G =(\{S\},\ \{a,\ b\},\ \{S \to aSb,\ S \to \varepsilon\},\ S)\) which generates strings of the form \(a^nb^n\)

1.3.1.4. Language¶

A formal language is a set of strings formed from an alphabet, according to specified grammar rules.

1.3.1.4.1. Mathematical formalization¶

Let \(\Sigma\) an alphabet, and \(L \subseteq \Sigma^*\) be a formal language where each string of \(L\) is a string of symbols formed from \(\Sigma\)

1.3.1.4.2. Language example¶

From the previous examples, consider :

\(\Sigma = \{a,\ b\}\) an alphabet

\(G = (\{S\},\ \{a,\ b\},\ \{S \to aSb,\ S \to \varepsilon\},\ S)\) a given grammar

\(L = \{a^nb^n \mid n \geq 0\}\) is a language