Auf Pausenhof.de findest du viele Arbeiten, Facharbeiten und Referate für die Schule.

Referate und Hausarbeiten : Informatik

< zurück zu Referate - Informatik

Chomsky Hierarchie

Kurzreferat zu Sprachen und Gramatiken in Bezug auf Unterteilung in Typen



1. Grammatik und Sprache
- Notation
- Definition Grammatik
- Bestandteildefinition
- Definition Formale Sprache
- Definition Aufzählbare Sprachen
- Definition Entscheibare Sprachen
- Definition Reguläre Sprachen

2. Typ-0-Sprachen
- Typ-0-Grammatik
- Beispiel
- Turingmaschine

3. Typ-1-Sprachen
- kontextsensitive Grammatik
- Beispiel
- linear beschränkter Automat

4. Typ-2-Sprachen
- kontextfreie Grammatik
- Beispiel
- Kellerautomaten

5. Typ-3-Sprachen
- Reguläre Grammatik
- Beispiel
- endlicher Automat


1. Grammatik und Sprache

1.1 Notation:
Nichtterminalsymbole werden in Backus-Naur-Form, in spitzen Klammern < >, gesetzt.
Der Pfeil ® einer Produktionsregel wird durch das Zeichen ::= dargestellt.
Alternativen werden durch einen senkrechten Strich ½ getrennt.
Geschwungene Klammern {} bedeuten Wiederholungen und eckige Klammern [] umschließen optionale Teile.



1.2 Definition Grammatik:
Eine Grammatik G=(T,N,P,S) ist ein Viertupel mit:
• T endliche Menge der terminalen Symbole
• N endliche Menge der nichtterminalen Symbole, T Ç N = Ø
• P Produktionssystem mit endlich vielen Produktionsregeln
• S 0 N, Startsymbol

1.3 Bestandteildefinition:
Terminale T: Das Alphabet der Sprache. Terminalsymbole sind Zeichen oder Wörter, die nicht mehr weiter zerlegt werden können und mit denen jeder Satz einer Sprache formuliert wird.
Tdeutsch = {a, ...z, A, ...Z, der, die , das, Professor, Studentin, ...}
T*: Menge aller Wörter, die durch die Hintereinanderreihung endlich vieler Terminalsymbole einschließlich des leeren Wortes e, erzeugt werden können

Nichtterminale N: Hilfssymbole, mit deren Hilfe die Grammatikregeln formuliert werden können. Jedes nichtterminale Symbol entspricht einer Variablen und läßt sich in eine Folge anderer nichtterminaler und terminaler Symbole umschreiben.
Ndeutsch = {<Satz>...

Du möchtest das komplette Referat lesen?

Gib einfach deine E-Mail-Adresse ein, damit wir das komplette Referat kostenlos als PDF zur Verfügung stellen können! Du kannst es dann bearbeiten und ausdrucken.

* Pflichtangaben