Regel- und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen

Abstract

Wir untersuchen kontextfreie Sprachen in Bezug auf die Beschreibungskomplexitäten Regel- und Symbolkomplexität nach Anwendung ausgewählter Sprachoperationen (z. B. Vereinigung). Kontextfreie Sprachen werden durch kontextfreie Grammatiken allein durch Platzhalter/ Variablen, Buchstaben, Ersetzungsregeln und eine für kontextfreie Grammatiken festgelegte Vorgabe der Regelanwendung erzeugt. Eine regel-minimale (kontextfreie) Grammatik ist eine kontextfreie Grammatik, die die geringste Regelanzahl für die kontextfreie Sprache L, die sie erzeugt, hat, bezogen auf alle kontextfreien Grammatiken, die L erzeugen. Bei Konstruktion einer regel-minimalen Grammatik G, die eine Sprache L erzeugt, gibt es die Möglichkeit, L in andere Sprachen zu zerlegen, die unter Anwendung gewisser Operationen wieder L ergeben. So könnte L derart in Sprachen L1 und L2 zerlegt werden, dass mithilfe der Operation Vereinigung gerade L = L1 [ L2 gelte. Anschließend werden für L1 und L2 regel-minimale Grammatiken G1 bzw. G2 konstruiert. Die Regelkomplexitäten von G, G1 und G2 können nun verglichen werden: So könnte die addierte Anzahl der Regeln von G1 und G2 größer sein als die von G – oder umgekehrt oder gleich. Wir zeigen in dieser Arbeit, welche Komplexitätsänderungen für regel-minimale Grammatiken bei der Sprachzerlegung prinzipiell möglich sind: Es sei Prod(L) die Anzahl an Regeln, die eine regel-minimale Grammatik benötigt, um eine kontextfreie Sprache L zu erzeugen. Für zwei natürliche Zahlen n und m ist dann CProd[ (n,m) = {Prod(L1 [ L2) | Prod(L1) = n, Prod(L2) = m, L1 und L2 sind kontextfreie Sprachen} die Menge möglicher Regelkomplexitäten, die zwei beliebige kontextfreie Sprachen mit der minimalen Regelanzahl n bzw. m unter Vereinigung [ haben können. Dies lässt sich analog für weitere Operationen definieren. Für m n sind die folgenden Aussagen ein Teil der wesentlichen Ergebnisse dieser Arbeit: • Unter der Operation Spiegelbild gilt CProd()R (n) = {n} . • Unter der Operation Vereinigung gilt 6, . . . , n + m + 2 2 CProd [ (n,m) = CProd[ (m, n) /3 n + m + 3, . . . für n 2,m 2. • Unter der Operation Konkatenation gilt n + 2, . . . , n + m + 1 2 CProd · (n,m) = CProd· (m, n) /3 n + m + 2, . . . für n 5,m 5. • Unter der Operation Kleene-Abschluss gilt CProd() (n) = 8>>< >>: {1} für n = 0 {1, 2} für n = 1 {2, . . . , n + 2} sonst. • Unter der Operation Homomorphismus (Menge aller Homomorphismen Hom) gilt CProdHom (n) =({0} für n = 0 {1, . . . , n} sonst. • Unter der Operation Inverser Homomorphismus (Menge aller inversen Homomorphismen Hom-1) gelten {0} = CProdHom-1 (0), N = CProdHom-1 (n) für n 1. • Unter der Operation Schnitt mit regulärer Sprache (Menge aller Schnitte mit regulärer Sprache Reg) gelten {0} = CProdReg (0), {0, 1} = CProdReg (1), N0 = CProdReg (n) für n 2. Zuvor Genanntes untersuchen wir zudem analog für symbol-minimale Grammatiken – hier werden die Anzahl der Platzhalter/Variablen und Buchstaben in den Regeln als Maß verwendet. Wir erhalten für die Mengen möglicher Symbolkomplexitäten unter Sprachoperationen im Wesentlichen – bezogen auf die Mengen möglicher Regelkomplexitäten unter Sprachoperationen – ähnliche Ergebnisse.