Informatik/EDV: Formale Grammatik
- Datum: 17.12.09
-
Thematische Einordnung:
Theoretische Informatik
- Tags: Theoretische_Informatik
Je mehr Sterne Sie vergeben, desto besser fanden Sie den Artikel.
Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi-Thue-Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau angewandt, um zum einen eine formale Sprache eindeutig zu beschreiben (d. h. um eindeutig festzulegen, ob ein Wort Element einer Sprache ist, oder nicht) und um zum anderen Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden mit Hilfe der Chomsky-Hierarchie klassifiziert.
Eine Grammatik ist ein 4-Tupel G=(V,∑,R,S) mit:
V: Alphabet von Variablen (Nonterminale)
∑: Alphabet der Terminale
R: einer endlichen Menge von Regeln (Produktionen) α —>β mit α Є (V U ∑ )^+ , β Є (V U ∑)^*
S: S Є V : Startvariable
Beispiel:
| GARI = ( | {S} | , { + , * , a , c , ) | } , | R, | S ) |
| V | , ∑ |
| R = { | S —> S + S | , i | ||
| S —> S * S | , ii | |||
| S —> ( S ) | , iii | |||
| S —> a } | , iv |
Grammatik erzeugt korrekt geklammert arithmetische Ausdrücke, z.B.:
| S ==> S * S | , ii | |
| ==> a * S | , iv | |
| ==> a * S * S | , ii | |
| ==> a * a * S | , iv | |
| ==> a * a * S * + S | ,i | |
| ==> a * a * ( S ) + S | , iii | |
| ==> a * a * ( S + S ) + S | , i | |
| ==> … ==> | ,iv | |
| ==> a * a * ( a + a ) + a | ,iv |
Für weitere Informationen sehen Sie die Seite Wikipedia an.
Literaturtipps & verwendete Quellen:
Verwandte Artikel:
- Theoretische_Informatik:
Wiki-Autor:
| Name: | Barbaros M. |
| Alter: | 32 |
| Fach: | Informatik/EDV, Mathematik |
| Ort: | Bayern |
| Preis: | 14,20 € |
Es macht mir Spaß Menschen zu motivieren und ihnen zu helfen Probleme beim Lernen zu überwinden.
| Schauen Sie sich diesen und viele weitere Nachhilfelehrer genauer an: |
