Worksheet

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Druckversion

Alphabet, Zeichen, Wort, Sprache

Definiere Alphabet, Zeichen, Wort und Sprache.











Bedeutende Probleme der formalen Sprachen

Nenne und beschreibe einige interessante Probleme im Zusammenhang mit formalen Sprachen.























Kleines Beispiel der deutschen Grammatik

Gib ein kleines Beispiel der deutschen Grammatik an.

































Leite beispielhaft ein Wort der Sprache ab. (Umgangssprachlich sagt man dazu im Kontext natürlichsprachlicher Grammatiken "Satz").











Definition Grammatik

Definiere Grammatik.























Beispiel: Grammatik zur Erzeugung der Dyck-Sprache D_2

Gib eine Grammatik zur Erzeugung der Dyck-Sprache D_2 an.























Gib drei Ableitungssequenzen an für das Wort ()[()]().























Gib die drei Syntaxbäume der Ableitungssequenzen an.























Links- und Rechtsableitungen

Definiere Linksableitung und Rechtsableitung.











Definiere eindeutige und mehrdeutige Grammatik.











Chomsky-Hierarchie

Definiere Phrasenstrukturgrammatik (Typ-0-Grammatik).











Definiere kontextsensitive Grammatik (Typ-1-Grammatik).











Definiere kontextfreie Grammatik (Typ-2-Grammatik).











Definiere reguläre Grammatik (Typ-3-Grammatik).











Definiere Typ-n-Sprache.











Gib jeweils ein Beispiel für eine Sprache jedes Typs an.











Reguläre Sprachen

Gib ein Beispiel einer regulären Grammatik an, außerdem die Herleitung eines Beispielwortes inklusive Syntaxbaum.























Beweise: \Sigma^{*} ist eine reguläre Sprache, d.h. eine Sprache vom Typ 3.























Beweise: Alle endlichen Sprachen sind vom Typ 3.























Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe oder in der nächsten Plenumssitzung klären kannst!