Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
17 Cards in this Set
- Front
- Back
|
Was gehört zur Beschreibung einer fromalen Sprache? |
1. Syntax: Menge von Vorschriften/Regeln, die den formal korrekten Aufbau von Wörtern/Sätzen angeben 2.Sematik: Bedeutung eines syntaktisch korrekten Satzes 3. Pragmatik: enthält subjektive Aspekte individueller Benutzer |
|
|
A |
Alphabet: endliche nichtleere Menge von Zeichen { a, ... ,z} |
|
|
W |
Wort über A: endliche Folge von Zeichen von A. |
|
|
|W| |
Länge von w |
|
|
Lamda |
leeres Wort, Länge 0 |
|
|
A^n |
Menge aller Wörter der Länge n |
|
|
A* |
Menge aller Wörter über A |
|
|
A+ |
Menge aller nichtleeren Wörter über A |
|
|
L |
Sprachen über A
|
|
|
Defintion: Ein formales System zur Beschreibung einer formalen Sprache L heißt erzeugend. |
, falls jese Wort w€L durch Verwendung dieses Systems nach endlich vielen Schritten erzeugt werden kann. |
|
|
Defintion: Ein formales System zur Beschreibung einer formalen Sprache L heißt analysierend. |
falls es zu jedem Wort w € A* nach endlich vielen Schritten angeben kann, ob w zu L gehört oder nicht.
|
|
|
Defintion: Ein formales System zur Beschreibung einer formalen Sprache L heißt operationell |
falls die Sprache durch einen Term aus Elementen definierter Basismengen und Operationen beschrieben wird |
|
|
Die Chomsky-Grammatik |
Eine Chomsky-Grammatik ist ein Tupel G= (N, T, P, S) mit N: Menge der Nonterminalsymbole T: Menger der Terminalsymbole P ⊂ ( N ∪ T)+ x ( N ∪ T)*: Regelmenge über N∪T bzw. Menge der Produktionen |
|
|
Überführbarkeit Definiton |
Gegeben: Regelmenge P, Worte v, w,∈ ( N∪T)* - v heißt unmittelbar überführbar in w ( v => w) genau dann wen es zu u, z ∈ ( N∪T)* und (δ→γ)∈P mit v= uδz^w=uγz gibt.
Gilt v=>*w, so heit v überführbar ind w. |
|
|
Sprache einer Chomsky-Grammatik |
Für eine Chomsky-Grammatik G = ( N, T, P, S) ist
L(G) := {w∈ T* | S=>* w}
die durch G erzeugte Sprache! |
|
|
Vereinbahrung 2.Terminalsymbole 3.Wörter |
1. Nonterminalsymbole: große lateinische Buchstaben. 2.Terminalsymbole: beliebige Zeichen, meist a,b,... 3.Wörter: u, v, w, oder δ, η, λ |
|
|
Problematik der Chomsky-Grammatik |
Es ist i.A nicht algorithmisch entscheibar, ob ein Wort zur Sprache einer vorgegebenen Grammatik gehört oder nicht. |
