Ben Tels wrote:
> > Context Sensitive has a very specific meaning here. Perhaps it would help if I
> > said that it is another name for Type 1 languages
>
> Not really
>
> > and it is recognized by finite
> > linear Turing Machines.
>
> Which puts you right back in the realm of context-free languages.
No, it gives you context-sensitive languages.
> >In context free languages the
> > only allowed production rules are of the form
> >
> > A-->aB
>
> That is incorrect. Context-free languages allow many forms of production rules,
> including
This was only a sample, not necessarily meant to be exhaustive. The primary
characteristic is that there is a SINGLE NON-TERMINAL on the left hand side of the
production rule.
> > whereas in context sensitive languages you can have production rules of the form
> >
> > aA-->aA
>
> Equivalent to A -> lambda.A
No. The point is that the left hand side can contain any STRING of NON-TERMINALS and
TERMINALS with at least one non-terminal.
> > bA-->ab
>
> ???? That's an interesting one. Not sure what would allow that.
A context-sensitive grammar would allow that. Context-free does not.
> > BA-->ABc
>
> Sure, why not?
>
> B -> A
> A -> Bc
>
> Together makes BA -> ABc
No. There is no production rule given for B itself. There is no production rule for A
itself. There is only a production rule for the COMBINATION BA.
> > In other words, what the terminal A can produce depends on the context in which
> > it occurs.
>
> Yes, the set of production rules.
No the context of the non-terminal. Above, there is no production rule for A itself.
There is only one for A in the context of having a preceding B.
> > > It is not. Context is an extension to CFL's.
> >
> > Context Sensitive is a class of formal language. It is also referred to as type
> > 1 languages and are parsed/produced by finite linear Turing machines.
>
> Which brings you back to the languages produced by finite automata. The Context-Free
> languages.
No, it does not. Let me give you an example. The simplest context-sensitive language
that I know is a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>. This would include strings
such as abc, aabbcc, aaabbbccc, aaaabbbbcccc,.... It would exclude strings such as
aabcbc.
The following set of production rules produces it.
S --> ASBC
S --> ABC
A --> a
aB --> ab
bB --> bb
CB --> BC
C --> c
Let's see what happens when we apply the production rules.
Production String
S --> ASBC ASBC
S --> ABC AABCBC
A --> a aABCBC
A --> a aaBCBC
aB --> ab aabCBC
Now here we have a choice. We could apply CB --> BC or C --> c. Let's try the last one
first.
C --> c aabcBC
C --> c aabcBc
We are now stuck. There is no production rule for B and none for cB. Therefore we
cannot produce a string of terminals from this point. Let's look at what happens if we
take the other option.
CB --> BC aabBCC
bB --> bb aabbCC
C --> c aabbcC
C --> c aabbcc
You simply cannot reproduce this with a context free grammar. Context sensitive
languages are not extensions of context free languages. They are a completely
different set of languages.
> Look, pick up "An Introduction to Formal Languages and Automata" and read chapters 5
> through 8. You will see that what you refer to as "Context
> Sensitive Languages" are not disjoint from the context-free ones
> (context is an extension of the CFG).
I'm not saying that they are disjoint. In fact, context free languages are a subset of
the context sensitive languages. This started when I mentioned context sensitive
languages and you said there was no such thing. Do you wish to retract that statement
now?
Drew Allen
|