SKEDSOFT
Definition of CFG: A context-free grammar is a 4-tuple (V, T, S, P) where
- V is a finite set called the variables
- T is a finite set, disjoint from V, called the terminals
- P is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
- S ÎV is the start variable.
If u, v and w are strings of variables and terminals, and A-> w is a rule of the grammar, we say that uAv yields uwv, written uAv Þuwv.
Example of CFG: Given a grammar G = ({S}, {a, b}, R, S). The set of rules R is
This grammar generates strings such as
abab, aaabbb, and aababb
If we assume that a is left parenthesis ‘(’ and b is right parenthesis ‘)’, then L(G) is the language of all strings of properly nested parentheses.
Right-Linear Grammar: In general productions have the form:
(V ÈT ) -> (V ÈT )* .
In right-linear grammar, all productions have one of the two forms:
V ->T *V
or V ->T *
i.e., the left hand side should have a single variable and the right hand side consists of any number of terminals (members of T) optionally followed by a single variable.
Right-Lin ear Gram mars and NFAs: There is a simple connection between right-linear grammars and NFAs, as shown in the following illustration.
As an example of the correspondence between an NFA and a right linear grammar, the following automaton and grammar both recognize the set of set of strings consisting of an even number of 0’s and an even number of 1’s.
Left-Linear Grammar
In a left-linear grammar, all productions have one of the two forms:
- V ->VT *
- or V ->T *
i.e., the left hand side must consist of a single varibale, and the right-hand side consists of an optional single variable followed by one number of terminals.
