Aufgabe aus Theoretischer Informatik:

Hallo Forum,
könntet Ihr bei einer Aufgabe weiterhelfen?

Aufgabenstellung:
$Zu \ zeigen:\ Eine\ kontextfreie\ Sprache \ L \subseteq X^* \setminus \lbrace \epsilon \rbrace ist\ genau\ dann\$$ rechtslinear,\ wenn\ sie\ durch\ eine\ Grammatik\ G=(N,X,S,P)\ mit$
$Produktionen\ der\ Gestalt\ A -> aB\ und\ A->a\ fuer\ a\in\ X\ und\ A,B \in N$
$erzeugbar\ ist.$
Was zu zeigen ist ist doch:
->Eine kf Sprache ist dann rechtslinear wenn sie von solchen Produktionen erzeugt wird.
<-Solche Produktionen erzeugen nur kf rechtslineare Grammatiken.

-> Steht doch eigentlich schon da? Oder kennt Ihr eine andere Def für kf rlineare Grammatiken?

<- Kf rechtslineare Grammatiken erzeugen reguläre Sprachen. Aus den Produktionen könnte ich einen Automaten bauen.

Geht das so?

Alex

Griffin

Ich nehme an du sprichst von einer rechtslinearen Grammatik.

Grammatik G = {N, Σ, P, S}

Es gilt: A -> wB || A -> w

A,B sind Element N
Und w ist ein Wort aus Σ*

Das Wort kann mit Gebrauch der Produktionen also nur auf der rechten Seite wachsen. Es wird immer ein Nichtterminal angefügt

Ja. Unten habe ich alles ein bißchen Abgekürtzt...