Construct a context-sensitive grammar that generates L:

L = {a^n b^m c^k|k>n, k>m}

I believe my productions should go along this lines:

A-> a|aBC|BC
B-> b|bBC
C-> c|Cc

The idea is to start with 2 c and keep always one more c, and then with C->c|Cc ad as much c as i want. How can my production for C remember the numbers of m and n.


Hint. Can you figure out a regular grammar such that for any $k, m, n$ with $k > n$ and $k > m$, there is a word in its language with that number of a, b and c (in any order)?

Hint. Did you know that you can sort with a context sensitive grammar? See an example for inspiration.


Maybe this?

// end of string marker X
S := TX

// sets up the count relationships
T := TT | AC | BC | C

// sets up the order relationships
BA := AB
CA := AC
CB := BC

// convert to terminals from back to front
Aa := aa
Ab := ab
Ac := ac
Bb := bb
Bc := bc
Cc := cc
CX := c

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.