Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Chomsky-Hierarchie EINFACH ERKLÄRT! | 2024
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 33 Zeilen
- willkommen zum heutigen Video über die homski Hierarchie also fangen wir gleich mal an man sieht hier in der Grafik erstmal alle sprachklassen es gibt zwar
- noch zwei weitere und zwar die dcfl deterministisch kontextfreien Sprachen welche von den kontextfreien Sprachen unterschieden werden können und die
- deterministisch kontexsensitiven Sprachen welche von den kontexsensitiven Sprachen unterschieden werden können in diesem Video werden wir uns allerdings
- mit den Hauptgruppen beschäftigen vielleicht mache ich ein anderes Video über diese Sprachgruppen man kann in der Grafik
- erkennen dass die Typ prachen eine Teilmenge aller Sprachen sind auch zeigt die Grafik dass es Sprachen gibt die Typ 2 sind aber nicht Typ 3 und so weiter
- ein weiterer Aspekt der hier deutlich wird ist dass es auch Sprachen außer die Typ Null Sprachen gibt das ist der Fall weil es ja nicht zu jeder Sprache eine
- Grammatik geben kann weshalb diese nicht zu den Typ Null Sprachen zählen können auch wichtig ist dass Typ 3 Typ 2 und Typ 1 alle eine Teilmenge der Typ Null
- Sprachen bilden aber ich denke ihr versteht wie man die Info Grafik interpretieren kann fangen wir als erstes Mal mit Typ Null Grammatiken an
- diese werden auch als unbeschränkte Grammatiken bezeichnet allgemein kann man sagen dass alle Grammatiken vom Typ Null sind jede Grammatik muss also vom
- Typ ull sein kann aber gleichzeitig von einem anderen spezifischeren Typen sein wichtig wie schon erwähnt heißt das nicht dass jede Sprache vom Typ Null ist
- Typ Null Grammatiken sind uneingeschränkt also man kann mit den Produktionen auch etwas wie Alpha geht nach Beta Gamma Delta
- bilden und auch Beta Gamma Delta y geht nach Z das sind jetzt einfach nur Repräsentanten für beliebige Elemente aus dem Alphabet und den
- variablen es gibt hier immer eine Touring Maschine welche die von einer Typ n0 Grammatik erzeugte Sprache erkennen kann das ganze gilt
- offensichtlicherweise auch umgekehrt nun zu den Typ 1 Grammatiken jetzt sind unsere Grammatiken leider nicht mehr beliebig sondern es gibt eine neue
- Einschränkung und zwar gilt jetzt dass der Betrag von der linken Seite der Produktion kleiner oder genau gleich lang wie die rechte Seite sein soll
- wichtig ist es hierfür die EPS Sonderregel zu kennen sonst kann man nicht mehr alle Sprachen bilden und werden unter anderem auch
- kontextsensitiv genannt jetzt können wir uns auch mal fragen welche Automat denn jetzt unsere Sprache erkennt also natürlich gibt es hier wieder eine ganz
- normale Touring masaschine weil unsere Grammatik ja auch die Bedingung von Typ Null erfüllt aber es gibt trotzdem auch einen spe Automaten für die Typ 1
- Sprachen also eine linear beschränkte touringmaschine allerdings ist das für den Anfang zu komplex weshalb wir das ganze jetzt erstmal so stehen
- lassen im nächsten Teil geht es jetzt um die Typ 2 Grammatiken unter anderem sind diese auch als kontextfreie Grammatiken bekannt die Einschränkung von den
- Kontext sensitiven Sprachen bleibt erhalten da Typ 2 ja auch immer vom Typ 1 ist was jetzt dazu kommt ist dass die linke Seite jetzt immer nur ein nicht
- Terminal oder auch variable genannt ist die Sprachen welche von den Typ 2 Grammatiken erstellt werden können kann man auch wieder in deterministisch und
- nicht deterministisch kontextfrei unterteilen das habe ich ja bereits erwähnt allerdings ist es am Anfang erstmal nur relevant zu verstehen welche
- grammatikalischen Regeln bei den kontextfreien Sprachen gelten denn deterministisch kontextfrei ist nur eine Teilmenge der kontextfreien Sprachen
- okay dann schauen wir uns jetzt mal wieder an welcher Automat unsere Sprache erkennt diesmal handelt es sich um einen kellerautomaten auch PDA genannt hier
- ist es wichtig zu verstehen dass dieser nach dem First in first out Prinzip funktioniert allerdings besprechen wir das Ganze in einem weiteren Video als
- letztes kommen jetzt die Typ 3 oder auch reguläre Grammatiken genannt diese sind für euch am Anfang erstmal die wichtigsten hier gelten alle
- Einschränkung die wir bis jetzt erwähnt haben plus dass die rechte Seite einer Produktion immer entweder aus einem Terminal steht also einem Buchstaben aus
- dem Alphabet oder einem Terminal gefolgt von einer Variable hier kann man jetzt auch noch zwischen links und rechts rekursiv unterscheiden dies muss dann
- aber einheitlich in der Grammatik sein zum Schluss schauen wir uns dann noch mal einen Automaten an da reguläre Sprachen endlich sind gibt es hier
- natürlich auch einen endlichen Automaten man kann zum Erkennen einer regulären Sprache einen NEA oder auch dea verwenden weil diese gleichmächtig sind
- in einem weiteren Video werde ich natürlich noch den NEA und erklären und genauso erklären wie man von einer regulären Grammatik auf den Automaten
- schließen kann
Zum Nachlesen
Chomsky-HierarchieSie ist eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, und wurde 1956 erstmals von Noam Chomsky beschrieben. Die …
Formale GrammatikFormale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …
Reguläre GrammatikEine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen …