Informatiker Board | formale Sprachen | Reguläre Grammatik erzeugen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Reguläre Grammatik erzeugen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Reguläre Grammatik erzeugen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Spender
Grünschnabel

Dabei seit: 19.07.2012
Beiträge: 4

Reguläre Grammatik erzeugen

Zitatantwort auf diesen Beitrag erstellen

So noch eine.

Eine reguläre Grammatik, die die Sprache L erzeugt
L={a(bc)^nd|n>=0}

Wie fang ich da grundlegend an? Wie viele Platzhaltervariablen brauche ich und wonach wird ersetzt bzw. abgeleitet?

Es dankt
der SPender

21.07.2012 14:43

Nehmen Sie Spender in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Der Weg ist, soweit keiner eine andere Lösung postet, dieser:
Grammatik in reguläre Grammatik umformen

VG,

Karlito

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 21.07.2012 21:38.

21.07.2012 21:37

Nehmen Sie Karlito in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ich löse das Beispiel mal, weil mir gerade langweilig ist.

Als erstes habe ich einen Automaten erstellt, welcher der Grammatik entspricht. Dieses Beispiel hier ist so günstig, dass man sofort die Grammatik ablesen kann. Der Automat ist im Anhang zu finden. Die Produktionen lassen sich direkt ablesen. Der Finalzustand hat eine Epsilon-Produktion.

$[latex]G = \{\{S,A,B,C,D,a,b,c,d\}, \{a,b,c,d\}, P, \{S\}\}[/latex]$ mit

$[latex] \begin{array}{rcl} P = \{ S & \rightarrow & aA, A & \rightarrow & bB, B & \rightarrow & cC, C & \rightarrow & dD, D & \rightarrow &cC, D & \rightarrow & \epsilon \} \end{array} [/latex]$

Karlito hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Karlito: 24.07.2012 13:21.

24.07.2012 11:13

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Reguläre Grammatik erzeugen