Greibach normal form

Greibach normal form

In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form::A o alpha X or:S o lambdawhere "A" is a nonterminal symbol, α is a terminal symbol, "X" is a (possibly empty) sequence of nonterminal symbols not including the start symbol, "S" is the start symbol, and "λ" is the null string.

Observe that the grammar must be without left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. (Some definitions do not consider the second form of rule to be permitted, in which case a context-free grammar that can generate the null string cannot be so transformed.) This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.

Given a grammar in GNF and a derivable string in the grammar with length "n", any top-down parser will halt at depth "n".

Greibach normal form is named after Sheila Greibach.

ee also

*Backus-Naur form
*Chomsky normal form
*Kuroda normal form

References

* John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. "(See chapter 4.)"


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… …   Wikipedia

  • Chomsky normal form — In computer science, a context free grammar is said to be in Chomsky normal form if all of its production rules are of the form: or or where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S …   Wikipedia

  • Kuroda normal form — In formal language theory, a grammar is in Kuroda normal form iff all production rules are of the form:: AB rarr; CD or: A rarr; BC or: A rarr; B or: A rarr; α where A, B, C and D are nonterminal symbols and α is a terminal symbol.Every grammar… …   Wikipedia

  • Sheila Greibach — (1939 ) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles.She worked with Seymour Ginsburg… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • List of University of California, Los Angeles people — Lists of notable alumni, faculty, and current students of the University of California, Los Angeles. Contents 1 Notable alumni 1.1 Nobel laureates 1.2 Academia, science and technology 1.3 …   Wikipedia

  • Henry Samueli School of Engineering and Applied Science — The Henry Samueli School of Engineering and Applied Science at UCLA (also known as HSSEAS) was opened with an enrollment of 379 students in the fall of 1945 [ [http://www.engineer.ucla.edu/history/timeline41 54.html UCLA Engineering School… …   Wikipedia

  • List of computing topics — Originally, the word computing was synonymous with counting and calculating, and the science and technology of mathematical calculations. Today, computing means using computers and other computing machines. It includes their operation and usage,… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • GNF — can refer to:* GameznFlix, and online US video game rental subscription service. * GNF 1 and GNF 2, Moroccan football divisions. * Greibach normal form, a computer science context free grammar. * Guinean franc, the ISO 4217 code for the currency… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”