Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.25673/32915
Titel: Regel- und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen
Autor(en): Harbich, Ronny
Gutachter: Dassow, JürgenIn der Gemeinsamen Normdatei der DNB nachschlagen
Körperschaft: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik
Erscheinungsdatum: 2020
Umfang: vii, 142 Seiten
Typ: HochschulschriftIn der Gemeinsamen Normdatei der DNB nachschlagen
Art: Dissertation
Tag der Verteidigung: 2019
Sprache: Deutsch
Herausgeber: Prosodia, Verlag für Musik und Literatur, Tangermünde
URN: urn:nbn:de:gbv:ma9:1-1981185920-331116
Schlagwörter: Theoretische Informatik
Zusammenfassung: 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.
URI: https://opendata.uni-halle.de//handle/1981185920/33111
http://dx.doi.org/10.25673/32915
Open-Access: Open-Access-Publikation
Nutzungslizenz: (CC BY-SA 4.0) Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International(CC BY-SA 4.0) Creative Commons Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International
Enthalten in den Sammlungen:Fakultät für Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Harbich_Ronny_Dissertation_2019.pdfDissertation1.18 MBAdobe PDFMiniaturbild
Öffnen/Anzeigen