Context sensitive grammar

No开发者_C百科am Chomsky - formal languages - type 1 - context sensitive grammar

Does AB->BA violate the rule? I assume it does. A -> aAB does not violate condition? aAB->ABc violates condition?

Using the wikipedia link provided, you can answer each question if you can map your production rules to the form:

iAr -> ibr, where A is a single non-terminal, i and r are (possibly empty) strings of terminals and non-terminals, and b is a non-empty string of terminals and non-terminals.

In other words, look at each of your rules, and try to make suitable choices for i, A, r, and b.

Before we look at your questions, let's look at some hypothetical examples:

Is CRC -> CRRRRRC a valid context-sensitive rule?

Yes. I can choose i=empty, A=C, r=RC, and b=CRRRR. Note, I could have made other choices that work, too.

Is xYz -> xWzv a valid context-sensitive rule?

No. There is no choice for i, A, and r that allow a match. If I chose i=x A=Y, r=z, and b=W, that trailing v screws things up.

Is xY -> xWzv a valid context-sensitive rule?

Yes. I can choose i=x, A=Y, r=empty, and b=Wzv.

This is the scheme you should use to answer your questions. Now, let's look at those:

1. AB -> BA: Assume you choose either A or B to be your single non-terminal. The choice fixes i and r (one will be empty, the other will be the non-terminal you didn't choose). Is there a string of the form ibr that can match based on how you fixed i and r? In other words, can you choose the string to replace b that maps to your rule?

2. A -> aAB. I hope the choice of your single non-terminal on the left is intuitively obvious. This choice will again fix i and r. Does the right map to a suitable ibr form where b is a nonempty string of terminals and nonterminals?

3. aAB -> ABc. Again, choose A or B to be your single non-terminal. This fixes i and r. Is there a choice that allows you to choose a suitable ibr?