This HTML5 document contains 27 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n10	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Greibach_normal_form

rdfs:label

Greibach normal form

rdfs:comment

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name. More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form: Observe that the grammar does not have left recursions.

owl:sameAs

yago-res:Greibach_normal_form freebase:m.0f3d0

dbp:wikiPageUsesTemplate

dbt:Cite_book dbt:Var

dct:subject

dbc:Formal_languages

prov:wasDerivedFrom

n10:Greibach_normal_form?oldid=992049124&ns=0

dbo:wikiPageID

53928

dbo:wikiPageLength

3047

dbo:wikiPageRevisionID

992049124

dbo:wikiPageWikiLink

dbr:Chomsky_normal_form dbr:Sheila_Greibach dbc:Formal_languages dbr:Production_(computer_science) dbr:Context-free_grammar dbr:Top-down_parsing dbr:Empty_string dbr:Context-free_language dbr:Left_recursion dbr:Kuroda_normal_form dbr:Backus–Naur_form dbr:Terminal_and_nonterminal_symbols dbr:Pushdown_automaton dbr:Formal_language

dbo:abstract

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name. More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form: where is a nonterminal symbol, is a terminal symbol, is a (possibly empty) sequence of nonterminal symbols not including the start symbol and is the start symbol. Observe that the grammar does not have left recursions. Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is O(n4) in the general case and O(n3) if no derivation of the original grammar consists of a single nonterminal symbol, where n is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step. Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n.

foaf:isPrimaryTopicOf

n10:Greibach_normal_form