We develop different Models of Computation and study what classes of problems they can compute through Formal Languages.

Definitions

A string is a finite sequence of symbols in an alphabet .
- The reverse of a string is defined as .
A language is a set of strings.
- The reverse of a language is defined as , which contains all the strings in reverse. That is
The empty string is the string of length
The empty language is the set with no strings.
A grammar consists of a set of production rules. Each rule appears as a line comprising a symbol and a string separated by an arrow. The symbol is called a non-terminal and other symbols are called terminals. One variable is designated as the start non-terminal.
More formally, a grammar is a tuple where
- is a finite set of nonterminal symbols that is disjoint with the strings formed from .
- is a set of terminal symbols.
- A finite set of production rules.
- which denotes the start symbol.
The sequence of substitutions in the grammar needed to generate a string is called a derivation. All strings generated this way are called the language of the grammar denoted for grammar .
- A leftmost derivation is a derivation where we replace the leftmost nonterminal in the production rule first.
- If there is more than one derivation for a string, we say the string is generated ambiguously and the grammar is ambiguous.
- A language is inherently ambiguous if it can only be generated with an ambiguous grammar.

The Library