Wie stelle ich die Produktion für eine Kontextfreie Grammatik her?

Question

Hallo Community,

wie stelle ich die Produktionen für eine Kontextfreie Grammatik für die L1 = { a^m bⁿ cⁿ ∣ n,m ≥ 1}?

Für das Bespiel L2 = { aⁿ bⁿ c^m ∣ n,m ≥ 0} habe ich folgende Produktionen:

S -> AC              A -> aAb | ε             C -> cC | ε

Das geling mir einfacher, jedoch komme ich auf das Obere ( L1 ) nicht drauf. Ich dachte an etwas wie:

S -> AB
A -> a
B -> bBc | ε

Allerdings fehlt mir die Möglichkeit bei A -> a, weitere a's herzustellen, falls z.B. m = 4 ist o.ä.

Answer 1

Aloha :)

$$\text{zu L1)}\;\;S\to aXbYc\;\;;\;\;X\to aX\,|\,\epsilon\;\;;\;\;Y\to bYc\,|\,\epsilon $$$$\text{zu L2)}\;\;S\to XY\;\;;\;\;X\to aXb\,|\,\epsilon\;\;;\;\;Y\to cY\,|\,\epsilon $$

Comments

Perfekt, vielen Dank! :)