Chomsky-Hierarchie EINFACH ERKLÄRT! | 2024
Simplexity
https://www.youtube.com/watch?v=7g0cAaFDJeM

Transkript (automatisch erstellt)

0:00 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
0:07 noch zwei weitere und zwar die dcfl deterministisch kontextfreien Sprachen welche von den kontextfreien Sprachen unterschieden werden können und die
0:15 deterministisch kontexsensitiven Sprachen welche von den kontexsensitiven Sprachen unterschieden werden können in diesem Video werden wir uns allerdings
0:22 mit den Hauptgruppen beschäftigen vielleicht mache ich ein anderes Video über diese Sprachgruppen man kann in der Grafik
0:28 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
0:38 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
0:46 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
0:56 Sprachen bilden aber ich denke ihr versteht wie man die Info Grafik interpretieren kann fangen wir als erstes Mal mit Typ Null Grammatiken an
1:04 diese werden auch als unbeschränkte Grammatiken bezeichnet allgemein kann man sagen dass alle Grammatiken vom Typ Null sind jede Grammatik muss also vom
1:12 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
1:22 Typ Null Grammatiken sind uneingeschränkt also man kann mit den Produktionen auch etwas wie Alpha geht nach Beta Gamma Delta
1:30 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
1:39 variablen es gibt hier immer eine Touring Maschine welche die von einer Typ n0 Grammatik erzeugte Sprache erkennen kann das ganze gilt
1:48 offensichtlicherweise auch umgekehrt nun zu den Typ 1 Grammatiken jetzt sind unsere Grammatiken leider nicht mehr beliebig sondern es gibt eine neue
1:56 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
2:05 wichtig ist es hierfür die EPS Sonderregel zu kennen sonst kann man nicht mehr alle Sprachen bilden und werden unter anderem auch
2:13 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
2:22 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
2:31 Sprachen also eine linear beschränkte touringmaschine allerdings ist das für den Anfang zu komplex weshalb wir das ganze jetzt erstmal so stehen
2:41 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
2:50 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
3:02 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
3:11 nicht deterministisch kontextfrei unterteilen das habe ich ja bereits erwähnt allerdings ist es am Anfang erstmal nur relevant zu verstehen welche
3:18 grammatikalischen Regeln bei den kontextfreien Sprachen gelten denn deterministisch kontextfrei ist nur eine Teilmenge der kontextfreien Sprachen
3:27 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
3:36 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
3:44 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
3:53 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
4:01 dem Alphabet oder einem Terminal gefolgt von einer Variable hier kann man jetzt auch noch zwischen links und rechts rekursiv unterscheiden dies muss dann
4:10 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
4:17 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
4:26 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
4:34 schließen kann