Aptitude (12) ASP.NET (2) Automata (4) Browser (1) C (5) C# (1) C++ (10) Code (3) CSS (1) Data Structure (1) DATABASE (3) HTML (1) java (43) JSP (1) math (1) MySql (8) other (6) php (3) Servlet (3)

Thursday, 3 May 2012

Greibach normal form

a context-free grammar is in Greibach normal form, if all production rules are of the form:
A \to \alpha A_1 A_2 \cdots A_n
or
S \to \varepsilon
where A is a nonterminal symbol, α is a terminal symbol, A_1, A_2, \ldots, A_n is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and ε is the empty word.
Observe that the grammar must be without left recursions.

No comments:

Post a Comment