Validate string given Context Free Grammar in Java

Question

How can someone validate if a string is part of a context free Grammar? Not just virtually, but build an algorithm for it?

Given a context free grammar with rules such as

• V-> v1v2
• v1->1 | 1v1
• v2-> 2 | 2v2

It is obvious that this is the language 1^n 2^n. But how would you go about with an algorithm to verify if it actually is. I am trying to accomplish this in java.

Morehouse

Do you want to verify that a string is generated by a CFG, or that the language of the CFG is what you say it is? – Breault

If the string is valid, meaning it belongs to the context free language, whose context free grammar is provided. – Morehouse

Answer 1

You might want to look into Earley's algorithm or the CYK algorithm, which are two algorithms for deciding whether a string is generated by a context-free grammar. Earley's algorithm runs in time O(n³) for any string of length n regardless of the production rules in the grammar (though the constant term in the big-O notation depends on the grammar), while the CYK algorithm requires that the grammar first be converted to Chomsky normal form to guarantee O(n³) runtime.

Hope this helps!

Breault

Yeah it helps a lot. One more question related to your answer. Is it even possible to implement epsilon transitions? – Morehouse

Given that there is an equivalence between NFA with ε-moves and regular NFA's, the answer would be "yes is possible". Source: en.wikipedia.org/wiki/… – Badmouth

@StephenC- NFAs and DFAs are formalisms for regular languages, not context-free languages. – Breault