Type 2: Context-free grammars

Type 2: Context-free grammars
Context-free grammars generate the context-free languages. These are defined by rules of the form A I J with A a nonterminal and J a string of terminals and nonterminals. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton. Context free languages are the theoretical basis for the syntax of most programming languages.


Type 3: Regular grammars
Regular grammars generate the regular languages. Such aiii grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal. The rule S I _ is also here allowed if S does not appear on the right side of any rule. These languages are exactly all languages that can be decided by a finite state automaton. Additionally, this
family of formal languages can be obtained by regular expressions. Regular languages are commonly used to define search patterns and the lexical structure of programming languages.









Context- Free Grammar
A Context- Free Grammar (CFG) G is a 4-tuple (N,?,R,S) where :
1- N is a finite set of nonterminals or variables.
2- ? is a finite set of terminals.
3- R is a finite set of rules, each consisting of variables (the left- hand side) and a sentential form (the right- hand side).
4- S is the start symbol.
The binary relation ? on sentential forms is defined as follows:
Let u, v, and w be sentential forms then uAw? uvw iff A?v is a rule in R
? captures a single derivation step.
?* is the reflexive transitive closure of ?,
and L(G)={s??* / S?* s}