HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can every DCFG be converted to DGNF?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
caneverydgnfdcfgconverted

Problem

I know you can convert every context-free grammar into Greibach normal form grammar.

But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?

Solution

If by deterministic GNF you mean as a deterministic grammar that is also GNF then yes, here is the paper. Normal forms of deterministic grammars


It is shown that every strict deterministic language may be given a
strict deterministic grammar which is also in Greibach normal form.

EDIT
Here is a paper outlining the technique to do the conversion Strict deterministic grammars and Greibach normal form

Context

StackExchange Computer Science Q#27677, answer score: 4

Revisions (0)

No revisions yet.