Formale Grundlagen Übungsaufgaben mit Lösungen zum Thema Formale Sprachen vom Typ-3

Formale Grundlagen Formale Sprachen April 2022


Inhaltsverzeichnis
1 Übungen aus dem Vorlesungsskript 1
1.1 Typ 3 Übungen Folie 64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Lx . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Ly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Lx ∪ Ly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3


1 Übungen aus dem Vorlesungsskript
1.1 Typ 3 Übungen Folie 64
1.1.1 Lx


Übungsaufgabe:
Lx = all strings over Σ := {0, 1} with exactly one ”0”: 1*01*




Lösungsansatz:
L(G) := {w ∈ L | 1∗ 01∗ }
Σ := {1, 0}
N := {S, A}
P := {
S → 1S
S → 0A
A → 1A
A→ε
}




Überprüfen: genau ’0’ erzeugen
Start bei S:

S → 0A ”Regel 2”

0A → 0 ”Regel 4”




Überprüfen: genau ’1011’ erzeugen
Start bei S:

S → 1S ”Regel 1”

1S → 10A ”Regel 2”

10A → 101A ”Regel 3”

101A → 1011A ”Regel 3”

1011A → 1011 ”Regel 4”