|
Bei diesem Verfahren werden bestimmte Abschlusseigenschaften von kontextfreien Sprachen ausgenutzt.
Zum Einen sind kontextfreie Sprachen abgeschlossen gegenüber der Schnittmengenbildung mit Regulären Ausdrücken.
Zum Anderen sind sie abgeschlossen gegenüber Homomorphismen.
Kontextfreie Sprachen sind abgeschlossen gegenüber:
- Vereinigung
- Konkatenation
- Sternbildung
- Homomorphismus
- Schnitt mit regulären Sprachen
Das Verfahren wird nun verständlich:
1. Schritt
Kontextfreie Sprache L0 (hier: eine Dycksprache) ∩ regulärer Ausdruck = kontextfreie Sprache L1
2. Schritt
Homomorphismus angewandt auf eine kontextfreie Sprache (hier: L1) = kontextfreie Sprache L2 (hier: unsere Zielsprache)
| 
1
2
3
4
5
6
RA und Dycksprachen
