Frage

Provide context free grammars for the following languages.

(a) {a^mb^nc^n | m ≥ 0 and n ≥ 0 }
(b) {a^nb^nc^m | m ≥ 0 and n ≥ 0 }

If there were any other rules involved such as m = n or anything like that, I could get it, but the general m greater than or equal to zero? I'm pretty confused. and also I don't understand how a and b would be any different. Here was my shot at making a grammar out of this:

S1 --> S2 | e
S2 --> aS2bS2c | S3
S3 --> aS3 | S4
S4 --> bS4 | S5
S5 --> cS5 | c
War es hilfreich?

Lösung

Is a^mb^n m repetitions of a followed by n repetitions of b? It looks like you copy-pasted an assignment and neglected even to format it to be readable on this site.

Assuming I'm reading that correctly, moving on…

The key is that (in the first language) b and c are repeated an equal number of times. When you match a b you must simultaneously match a c. A production matching this subsequence would be

S1 => e
S1 => b S1 c

Note that there are two languages there so you need two answers. You aren't being asked for one grammar that handles both languages. (The main problem with that would be ambiguity in the case that n = m).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top