Cheap and Secure Web Hosting Provider : See Now

[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 : http://cs.stackexchange.com/questions/27677

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback