Question

Gegeben sei die Grammatik G = (V, Σ, S, P) mit V = {S, A}, Σ = {a, b, c} und den Produktionen

S → aS | Scc | aAc
A → bAbb | ∈.

a) Leiten Sie mit dieser Grammatik aus dem Startsymbol 4 Wörter ab, die nur Buchstaben aus Σ enthalten.
b) Geben Sie 4 Wörter w ∈ Σ* an, die mit dieser Grammatik aus dem Startsymbol nicht abgeleitet werden können. Begründen Sie, warum diese Wörter nicht abgeleitet werden können.
c) Geben Sie die Sprache L(G), die von dieser Grammatik erzeugt wird.

Answer 1

a) Leiten Sie mit dieser Grammatik aus dem Startsymbol 4 Wörter ab, die nur Buchstaben aus Σ enthalten.

\(S\stackrel{S\to aAc}{\longrightarrow} aAc \stackrel{A\to\varepsilon}{\longrightarrow} ac\)

\(S\stackrel{S\to aS}{\longrightarrow} aS \stackrel{S\to aAc}{\longrightarrow} aaAc\stackrel{?}{\longrightarrow}\dots\)

...

b) Geben Sie 4 Wörter w ∈ Σ* an, die mit dieser Grammatik aus dem Startsymbol nicht abgeleitet werden können.

\(\varepsilon\), \(a\), \(b\), \(c\)

c) Geben Sie die Sprache L(G), die von dieser Grammatik erzeugt wird.

Leite weitere Wörter ab bis du ein Muster erkennst