Membership for a context sensitive grammar

Thread view:

Alex - 14 Sep 2006 14:36 GMT

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!

Reply to this Message

Oliver Wong - 14 Sep 2006 15:47 GMT

>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

Reply to this Message

Alex - 14 Sep 2006 15:57 GMT

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

Reply to this Message

Oliver Wong - 14 Sep 2006 16:19 GMT

>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

Reply to this Message

Patricia Shanahan - 14 Sep 2006 16:03 GMT

>> I have to write a java program to test if a word w € L(G) for a
>> context sensitive grammar G.
[quoted text clipped - 17 lines]
> 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

Reply to this Message

Membership for a context sensitive grammar

Free Magazines