World's most popular travel blog for travel bloggers.

[Solved]: Can every DCFG be converted to DGNF?

, , No Comments
Problem Detail: 

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?

Asked By : user978734

Answered By : lPlant

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback