Membership for a context sensitive grammar

[Alex]

I have to write a java program to test if a word w ¤ L(G) for a context
sensitive grammar G.

Can anybody help me?

Thx in advance!

 

[Oliver Wong]

I have to write a java program to test if a word w ¤ L(G) for a context
sensitive grammar G.

Can anybody help me?

http://en.wikipedia.org/wiki/Context-sensitive_grammar
<quote>
The decision problem that asks whether a certain string s belongs to the
language of a certain context-sensitive grammar G, is PSPACE-complete.
Indeed, there are even some context-sensitive grammars whose fixed grammar
recognition problem is PSPACE-complete.
[...]
That makes them totally unworkable for practical use, as the general
algorithm would take exponential time. Ongoing research on computational
linguistics has focused on formulating other classes of languages that are
"mildly context-sensitive" whose decision problems are feasible, such as
tree-adjoining grammars, coupled context-free languages, and linear
context-free rewriting systems. The languages generated by these formalisms
properly lie between the context-free and context-sensitive languages.
</quote>


- Oliver

 

[Alex]

I knew that this was a great decidability problem....but isn't there any
algorithm to do it ?

 

[Patricia Shanahan]

I have to write a java program to test if a word w ¤ L(G) for a
context sensitive grammar G.

Can anybody help me?

http://en.wikipedia.org/wiki/Context-sensitive_grammar
<quote>
The decision problem that asks whether a certain string s belongs to the
language of a certain context-sensitive grammar G, is PSPACE-complete.
Indeed, there are even some context-sensitive grammars whose fixed
grammar recognition problem is PSPACE-complete.
[...]
That makes them totally unworkable for practical use, as the general
algorithm would take exponential time. Ongoing research on computational
linguistics has focused on formulating other classes of languages that
are "mildly context-sensitive" whose decision problems are feasible,
such as tree-adjoining grammars, coupled context-free languages, and
linear context-free rewriting systems. The languages generated by these
formalisms properly lie between the context-free and context-sensitive
languages.
</quote>

Most programming languages, including Java, are really context
sensitive. Whether:

a = b+c;

is a valid Java statement depends on whether a, b, and c have been
declared, and if so, their declared types.

The usual solution is to separate the rules into a very tractable
grammar, always context free, and a set of additional rules about
declarations etc.

Is there any possibility of doing that sort of translation on your
grammar? It is almost essential if this is a real problem, requiring a
practical solution.

If not, if it is e.g. homework, consider treating it in two pieces, and
algorithm question and a Java coding question. First look for an
algorithm, in any language. Once you understand the algorithm, code it
in Java.

Patricia

 

[Oliver Wong]

I knew that this was a great decidability problem....but isn't there any
algorithm to do it ?

Yes, such an algorithm exists. Tiny at
http://www.gittens.nl/grammar.html is a proof of concept parser generator
for context-sensitive grammars. It generates C++ code. If you can (or won't)
read the source code, you could try reading the articles posted on that
site, or contacting the author directly.

- Oliver