A string over an alphabet is a finite sequence of symbols from the alphabet. A string with no symbols is called the empty string and is denoted by the greek symbol lambda. We can define other operations on strings like concatenation and reversal. A central issue in the theory of computation is the representation of languages by finite specifications. The first example we use is regular expressions .
Regular languages are sets of strings that can be expressed as regular expressions.
The sequence of applications of some rule to produce a string is called a derivation. In this module we shall study a more complex type of language generator, called context-free grammars . Computer programs written in any programming language must satisfy rigid criteria to be syntactically correct and therefore amenable to interpretation by a machine. Context-free grammars are used extensively in modeling the syntax of programming languages. A compiler for a programming language must contain a parser, an algorithm to determine whether a given string is in the language of the grammar, and, if so, to construct the parse tree of the string.