Fachrat Informatik - Forum

Hi,
wenn man davon ausgeht, dass eine rechte Seite einer Produktion einer regulären Grammatik nur aus entweder einem Terminal oder einem Terminal gefolgt von einem Nichtterminal (rechtsregulär - s. Wikipedia) bestehen darf, so hast du recht.

Die angegebene Grammatik lässt sich allerdings leicht in eine äquivalente reguläre Grammatik umformen, indem man die erste Produktion durch die folgende ersetzt:
S -> eps | a1 | b1

Ich meinte eigentlich, dass die beiden anderen Produktionen beibehalten werden sollen. Also die Grammatik durch folgende Produktionen bestimmt ist:

S -> eps | a1 | b1
0 -> a1 | b1
1 -> a0 | b0 | a | b

Quoted

Original von aliaatreides
Hallo!

Uebung 6, Aufgabe 3 fragt nach einer regulaeren Grammatik die L:={w von {a,b}* | |w|a =|w|b MOD 2 } erzeugt.

In der Uebung haben wir (oder ich falsch mitgeschrieben...) von dem DEA die folgende Sprache abgeleitet:

S -> eps | 0
0 -> a1 | b1
1 -> a0 | b0 | a | b

Meiner Meinung nach, ist diese Sprache nicht regulaer, wegen S -> 0 mit 0 Variable...

Habt Ihr eine Idee wie kann man es loesen?

Danke, Alia

In der Vorlesung wurde die Chomsky-Hierarchie definiert. Für Typ 1,2,3 wurde die Einschränkung gemacht, dass für Regeln der Form u->v immer |u|<=|v| gelten muss (sprich keine Wortverkürzungen erlaubt sind). Da jedoch in diesem Fall niemals Grammatiken vom Typ 1,2,3 für Sprachen, die das leere Wort enthalten möglich wären, wurde zudem eine folgende Definition gemacht:
Haben wir eine Grammatik G=(V, Sigma, P, S) vom Typ 1, 2 oder 3 und ist zudem epsilon in L(G) gefordert (das leere Wort gehört zur Sprache und muss von der Grammatik G erzeugt werden können), dann sei die Regel "S->epsilon" zugelassen, aber nur dann wenn S auf keiner rechten Seite einer Produktion aus P vorkommt.

Die von Dir angegebene Grammatik
ist demnach fast eine gültige Typ-3-Grammatik (reguläre Grammatik), da folgendes gilt:
- S->eps ist enthalten und S taucht nie auf einer rechten Seite auf.
- Für alle Regeln der Form u->v gilt sonst immer |u|<=|v|.
- Es gilt für u->v immer: |u|=1 und u ist eine Variable.
- Es gilt für u->v immer: v besteht entweder aus einem einzelnen Terminalsymbol oder aus einem Terminalsymbol gefolgt von einer Variablen. Hier ist jedoch ein Widerspruch an der Stelle (*) aufgetreten. Dies lässt sich jedoch leicht wieder gerade biegen, wie schon derSmutje vor mir gesagt hat. Einfach die Regel S->0 ersetzen durch S->a1 und S->b1.