Ch 8. Automata and Grammars
8.1 Languages and Grammars
In IT, the concept of a language extends far beyond spoken or written communication. A formal language is a set of strings constructed from a finite set of symbols [latex]\Sigma[/latex], known as an alphabet, and governed by specific rules. These languages are foundational in programming, data processing, and automata theory.
A string (also see Section 5.1) is a finite sequence of symbols from [latex]\Sigma[/latex]. The set of all possible strings over [latex]\Sigma[/latex] is denoted by [latex]\Sigma^{*}[/latex], and a language is any subset of [latex]\Sigma^{*}[/latex].
Example 8.1
Let [latex]\Sigma = \{ 0, 1 \}[/latex]. Then [latex]\Sigma^{*}[/latex] includes strings like "", "0", "1", "01", and "110".
A language [latex]L \subseteq \Sigma^{*}[/latex] might be defined as all strings with an even number of [latex]1[/latex]s.
Formal languages are used to define the syntax of programming languages, describe communication protocols, and model computational processes.
A grammar is a set of rules that defines how strings in a language can be generated. Grammars are used to specify the structure of languages and are essential in compiler design and natural language processing.
A grammar [latex]G[/latex] is a 4-tuple (see Section 4.3) [latex](V, \Sigma, R, S)[/latex] where [latex]V[/latex] is a finite set of variables (non-terminal symbols), [latex]\Sigma[/latex] is a finite set of terminal symbols (the alphabet), [latex]R[/latex] is a finite set of production rules, and [latex]S[/latex] is the start symbol.
If we have a production [latex]\{ A, B \} \in R[/latex], then we write it as [latex]A \rightarrow B[/latex].
Example 8.2
Consider the grammar [latex]G = ( \{ S \} , \{ a, b \} , R, S)[/latex], where [latex]R[/latex] contains
[latex]S \rightarrow aSb \quad S \rightarrow \epsilon[/latex] (null string)
This grammar generates strings with equal numbers of [latex]a[/latex]’s and [latex]b[/latex]’s in the form of [latex]a^{n}b^{n}[/latex], such as "", "ab", "aabb", and "aaabbb".
A string [latex]w_{2}[/latex] is said to be directly derivable from another string [latex]w_{1}[/latex] in a grammar [latex]G[/latex] if there is a single application of a production rule in [latex]G[/latex] that transforms [latex]w_{1}[/latex] into [latex]w_{2}[/latex], that is,
If [latex]w_{1} \Rightarrow w_{2}[/latex], then [latex]w_{2}[/latex] is directly derivable from [latex]w_{1}[/latex]
Example 8.3
Given a rule [latex]A \rightarrow aB[/latex], and a string [latex]S = AB[/latex], then [latex]AB \Rightarrow aBB[/latex] is a direct derivation.
A string [latex]w_{2}[/latex] is derivable from [latex]w_{1}[/latex] if [latex]w_{2}[/latex] can be obtained from [latex]w_{1}[/latex] by applying zero or more production rules in a grammar [latex]G[/latex], that is,
If [latex]w_{1} \Rightarrow^{*} w_{2}[/latex], then [latex]w_{2}[/latex] is derivable from [latex]w_{1}[/latex]
Example 8.4
If [latex]S \Rightarrow AB \Rightarrow aB \Rightarrow ab[/latex], then [latex]ab[/latex] is derivable from [latex]S[/latex].
A derivation is a sequence of strings [latex]w_{0}, w_{1}, w_{2}, \cdots, w_{n}[/latex] such that [latex]w_{0}[/latex] is the start symbol, each [latex]w_{i+1}[/latex] is directly derivable from [latex]w_{i}[/latex], and [latex]w_{n}[/latex] is the final string.
Example 8.5
Given grammar rules [latex]S \rightarrow AB, A \rightarrow a, B \rightarrow b[/latex], the derivation of [latex]ab[/latex] from [latex]S[/latex] is [latex]S \Rightarrow AB \Rightarrow aB \Rightarrow ab[/latex].
The language generated by a grammar [latex]G[/latex], denoted [latex]L(G)[/latex], is the set of all strings composed entirely of terminal symbols that can be derived from the start symbol [latex]S[/latex] using the production rules of [latex]G[/latex], that is,
[latex]L(G) = \{ w \in \Sigma^{*} \mid S \Rightarrow^{*} w \}[/latex]
In formal grammars, the symbol [latex]\mid[/latex] typically means “or”, indicating a choice between alternatives. For example, <action> [latex]\rightarrow[/latex] book [latex]\mid[/latex] cancel [latex]\mid[/latex] status means the <action> can be book, cancel, or status. In some mathematical contexts, however, [latex]\mid[/latex] can also be interpreted as “given”, such as in the definition or the language generated by a grammar above ([latex]w \in \Sigma^{*}[/latex] “given” [latex]S \Rightarrow^{*} w[/latex]).
Example 8.6
If [latex]G[/latex] has rules [latex]S \rightarrow aS \mid \epsilon[/latex], then [latex]L(G) = \{ \epsilon, a, aa, aaa, \dots \}[/latex], that is, all strings of zero or more [latex]a[/latex]’s.
If you find yourself in the situation where you need to describe the syntax of programming languages and formal grammars formally, Backus-Naur Form (BNF) is a useful, formal notation. It is especially useful when designing compilers, specifying languages, and parsing algorithms.
A BNF grammar consists of:
- Non-terminal symbols: Abstract syntactic categories (e.g.,
<expression>, <term>). - Terminal symbols: Actual symbols of the language (e.g.,
+, *, a, b). - Production rules: Define how combinations of terminals and other non-terminals can replace non-terminals.
- Start symbol: The initial non-terminal from which derivations begin.
Each production rule in BNF has the form
<non-terminal> ::= <expression>
where <expression> is a sequence of terminals and/or non-terminals.
Example 8.7
Consider the following two production rules:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number> ::= <digit> | <digit> <number>
Grammars are classified into four types:
Type 0 (Unrestricted): No restrictions on production rules.
Type 1 (Context-sensitive): Rules depend on the surrounding context.
Type 2 (Context-free): Each rule has a single non-terminal on the left-hand side.
Type 3 (Regular): Rules are highly restricted and generate regular languages.
Regular grammars are the simplest and can be recognized by finite automata (see Section 8.2), making them suitable for tasks like tokenizing input in programming languages.
Example 8.8
The language of all strings over [latex]\{ a, b \}[/latex] that contain an even number of [latex]a[/latex]’s is a regular language:
[latex]L = \{ w \in \{ a, b \}^{*} \mid[/latex] number of [latex]a[/latex]’s in [latex]w[/latex] is even [latex]\}[/latex]
The language of balanced parentheses is a context-free language:
[latex]L = \{ w \in \{ (,) \}^{*} \mid w[/latex] is properly nested and matched parentheses [latex]\}[/latex]
An example of a grammar in this language is [latex]S \rightarrow SS \mid (S) \mid \epsilon[/latex].
The language of strings with equal numbers of [latex]a[/latex]’s, [latex]b[/latex]’s, and [latex]c[/latex]’s is a context-sensitive language:
[latex]L = \{ a^{n} b^{n} c^{n} \mid n \geq 1 \}[/latex]
Two grammars [latex]G_{1}[/latex] and [latex]G_{2}[/latex] are said to be equivalent if they generate the same language, that is, [latex]L(G_{1}) = L(G_{2})[/latex]. This means that every string derivable from the start symbol of [latex]G_{1}[/latex] using its production rules is also derivable from the start symbol of [latex]G_{2}[/latex] using its own rules, and vice versa.
Formally, let [latex]G_{1} = (V_{1}, \Sigma, R_{1}, S_{1})[/latex] and [latex]G_{2} = (V_{2}, \Sigma, R_{2}, S_{2})[/latex]. Then [latex]G_{1}[/latex] and [latex]G_{2}[/latex] are equivalent if
[latex]\{ w \in \Sigma^{*} \mid S_{1} \Rightarrow^{*} w[/latex] using [latex]R_{1} \} = \{ w \in \Sigma^{*} \mid S_{2} \Rightarrow^{*} w[/latex] using [latex]R_{2} \}[/latex]
Example 8.9
Let [latex]G_{1}[/latex] and [latex]G_{2}[/latex] be to grammars over the alphabet [latex]\Sigma = \{ a, b \}[/latex], such that
[latex]G_{1}: S \rightarrow aSb \mid \epsilon[/latex]
[latex]G_{2}: S \rightarrow aX, X \rightarrow Sb \mid \epsilon[/latex]
Both grammars generate the language [latex]L = \{ a^{n} b^{n} \mid n \geq 0 \}[/latex]. So [latex]G_{1}[/latex] and [latex]G_{2}[/latex] are equivalent.
A Context-Free Interactive Lindenmayer Grammar (CFILG) is a specialized type of formal grammar that incorporates context-free production rules and interactive mechanisms. It is used primarily in modelling growth processes, parallel rewriting systems, and interactive simulations, especially in biological and graphical domains.
A CFILG consists of an alphabet, an axiom, and production rules. The alphabet ([latex]\Sigma[/latex] is a finite set of symbols, including variables and constants. The axiom ([latex]\omega[/latex]) is the initial string from which derivations begin. The production rules ([latex]P[/latex]) are context-free rules of the form [latex]A \rightarrow w[/latex], where [latex]A[/latex] is a single symbol and [latex]w[/latex] is a string of symbols.
Interaction rules explain how outside factors, such as user input or environmental conditions, can change how the grammar works. At each step, all applicable rules are usually applied simultaneously rather than sequentially. The grammar is called context‑free because each rule replaces a single symbol without looking at the symbols around it, unlike context‑sensitive grammars, which depend on neighbouring symbols. The interactive feature allows the grammar to adjust its behaviour based on external conditions, making it useful for modelling adaptive systems, such as plant growth that responds to light or obstacles.
Example 8.10
Let [latex]\Sigma = \{ A, B \}, \omega = A[/latex], and rules [latex]A \rightarrow AB, B \rightarrow A[/latex]. In a CFILG, the interaction rule might say if the user clicks, apply [latex]B \rightarrow \epsilon[/latex] (remove [latex]B[/latex]) or if the temperature > threshold, apply [latex]A \rightarrow AA[/latex]. This allows the system to evolve in response to external conditions.
A string [latex]w_{2}[/latex] is directly derivable from a string [latex]w_{1}[/latex] in a CFILG if [latex]w_{2}[/latex] is obtained by applying a single context-free production rule to one or more symbols in [latex]w_{1}[/latex], in parallel, possibly influenced by interactive conditions, that is,
If [latex]w_{1} \Rightarrow w_{2}[/latex], then [latex]w_{2}[/latex] is directly derivable from [latex]w_{1}[/latex].
Example 8.11
Given a rule [latex]A \rightarrow AB[/latex], and [latex]w_{1} = ACB[/latex], if interaction allows only [latex]A[/latex] to rewrite, then [latex]w_{2} = ABCB[/latex].
A string [latex]w_{2}[/latex] is derivable from [latex]w_{1}[/latex] if [latex]w_{2}[/latex] can be obtained from [latex]w_{1}[/latex] by applying zero or more parallel rewriting steps, each governed by context-free rules and possibly modified by interactive inputs, that is, [latex]w_{1} \Rightarrow^{*} w_{2}[/latex].
Example 8.12
If [latex]w_{1} = A[/latex], and rules are [latex]A \rightarrow AB[/latex] and [latex]B \rightarrow BA[/latex], then [latex]w_{2} = ABBA[/latex] is derivable from [latex]w_{1}[/latex] through multiple steps.
A derivation in a CFILG is a sequence of strings [latex]w_{0} \Rightarrow w_{1} \Rightarrow w_{2} \Rightarrow \cdots \Rightarrow w_{n}[/latex], where [latex]w_{0}[/latex] is the initial axiom (start string), each [latex]w_{i+1}[/latex] is directly derivable from [latex]w_{i}[/latex] using parallel application of rules, and the process may be influenced by interactive conditions at each step.
Example 8.13
Let [latex]\omega = A[/latex] and rules [latex]A \rightarrow AB[/latex] and [latex]B \rightarrow A[/latex]. Then a derivation might be
[latex]A \Rightarrow AB \Rightarrow ABA \Rightarrow ABAAB \Rightarrow \cdots[/latex]
The language generated by a CFILG is the set of all strings composed of terminal symbols that can be derived from the initial axiom [latex]\omega[/latex] through parallel rewriting steps, possibly influenced by interactive inputs, that is,
[latex]L(G) = \{ w \in \Sigma^{*} \mid \omega \Rightarrow^{*} w[/latex] under CFILG rules and interactions [latex]\}[/latex]
Example 8.14
If [latex]\omega = A[/latex] and rules are [latex]A \rightarrow AB[/latex] and [latex]B \rightarrow A[/latex], then [latex]L(G)[/latex] includes strings like [latex]A[/latex], [latex]AB[/latex], [latex]ABA[/latex], and [latex]ABAAB[/latex]. If interaction turns off [latex]B \rightarrow A[/latex], then the language changes accordingly.
Real-World Example 8.1: Designing a Chatbot Command Language
Suppose you work for a company that is developing a customer service chatbot that responds to commands typed by users. To ensure the chatbot understands and processes input correctly, you need to define a formal language using a context-free grammar. The alphabet is
[latex]\Sigma[/latex] = {book, cancel, status, flight, hotel, car, ID, number}
The grammar rules are as follows:
<command> ::= <action> <object> [<details>]
<action> ::= book [latex]\mid[/latex] cancel [latex]\mid[/latex] status
<object> ::= flight [latex]\mid[/latex] hotel [latex]\mid[/latex] car
<details> ::= ID <number>
<number> ::= any sequence of digits
The square brackets [ ] are used to indicate that part of the grammar is optional.
Examples of valid strings are book flight, cancel hotel ID 12345, and status car ID 98765. These strings are derivable from the grammar and form part of the language generated by the chatbot’s command grammar.
An interactive extension of this using CFILG is that if the user is logged in, the chatbot allows commands such as cancel flight ID 12345. If the user is not logged in, the grammar does not allow the cancel flight command because it is not derivable without an authentication context.
