patternMinor
Can every DCFG be converted to DGNF?
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?
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
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.