Kontextfreie Grammatiken

Question 1

Welche Sprachen werden mit kontextfreien Grammatiken assoziiert?

Answer 1

Kontextfreie Sprachen
- reguläre Sprachen
- viele mehr

Question 2

Welche Maschinen erkennen Kontextfreie Grammatiken?

Answer 2

Kellerautomaten

Question 3

Wann wird eine Sprache als Kontextfrei bezeichnet?

Answer 3

Wenn sie von einer kontextfreien Grammatik erzeugt werden kann

Question 4

Nenne die formale Definition einer kontextfreien Grammatik

Answer 4

Question 5

Wann ist eine Grammatik mehrdeutig?

Answer 5

Wenn gleiche Strings auf unterschiedliche Weisen erzeugt werden können

Question 6

Wann ist ein String mehrdeutig?

Answer 6

Wenn er durch seine Grammatik unterschiedlich erzeugt werden kann

Question 7

Welche Sprachen nennt man von Natur aus mehrdeutig?

Answer 7

Solche, die nur von mehrdeutigen Grammatiken erzeugt werden können

Question 8

Definiere die Chomsky Normalform

Answer 8

Question 9

Wie erzeugt man aus einer Grammatik die Chomsky Normalform?

Answer 9

1. make a new start variable appears on the right
2. Remove ε-rules
3. Einheitsregeln entfernen
4. Convert the remaining rules into the proper form by adding additional vari- ables and rules

Question 10

Definiere das Pumping Lemma für kontextfreie Grammatiken

Answer 10

Question 11

Wie wird die Pumpinglänge p für kontextfreie Grammatiken gesetzt?

Answer 11

Let b be the maximum number of symbols in the right-hand side of a rule