0

Do we need to convert a context-free grammar into Chomsky normal form first to convert it into Greibach normal form?

Improve this question

1 Answer 1

Reset to default
1

This question might be better suited to https://cs.stackexchange.com/, but there are also plenty of people who can answer it here.

The answer is no, you do not need to go through Chomsky Normal form. There is a method in the textbook: Hopcroft, J.E & Ullman J.D. (1969) Formal Languages and their relation to Automata, Addison-Wesley, pp.55-57. However, most simple convertions do go through Chomsky Normal Form first. Other techniques are longer and use Weak Greibach Normal Form as an intermediate step.

If you want more details on the method, there are plenty of class notes available on the net; for example here, here; however, many class notes only show the route through CNF.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.