CODEWITHSUNDEEP
algorithmcontext-free-grammar
nmikhailov
nmikhailov

Reputation: 1423

Generating strings from context free grammars

The problem is implementing an algorithm, that generates all strings with length between l and r from given context free grammar G.

I have come up with simple approach: run BFS on grammar graph, remembering states. But it fails on some recursive rules:

(1)   S -> 0 | SSS | λ

I can't simply limit maximum string length, because rules can contain λ (empty strings), so non-terminals can reduce final string length. (eg. running (1) with l = 1, r = 2 will output only 0 in my implementation)

I also tried to limit maximum number of applied rules, but it is obviously wrong too.

How i can limit or change my algorithm, so it will never go in endless loop and will work correctly?

Upvotes: 4

Views: 2196

Answers (1)

amit
amit

Reputation: 178431

You can transform the grammer to Greibach normal form, and then each step1 in the creationis increasing the size of the produced word, and you will be able to limit the length of the word as initially explained in the question.

(1) except possibly the first, if the empty word is in the grammer

Upvotes: 3

Related Questions