Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Dienstag, 28. April 2015

Formale Sprachen und Automaten


Deutsch

Seit der 12. Klas­se sind for­ma­le Spra­chen und Au­to­ma­ten ei­nes mei­ner Lieb­lings­the­men. Da man bei den gan­zen De­fi­ni­tio­nen leicht mal durch­ein­an­der kom­men kann, ha­be ich ei­ne Über­sicht ent­wor­fen, und möchte die­se natürlich nie­man­dem vor­ent­hal­ten.

For­ma­le Spra­chen
TypRegeln der Formerzeugenbeschreibenerkennen
0αAβ → γallgemeine Chomsky-
Grammatik
Turingmaschine
1αAβ → αγβkontextsensitive
Grammatik
nichtdeterministische
linear beschränkte
Turingmaschine
2A → γkontextfreie
Grammatik
(erweiterte)
Backus-Naur-Form
nichtdeterministischer
Kellerautomat
3A → b | bB
(rechtsregulär)
A → b | Bb
(linksregulär)
reguläre
Grammatik
regulärer Ausdruckendlicher Automat
Le­gen­de:
b ... Ter­mi­nal
I. d. R. gilt: b ≠ ε
A ... Nicht­ter­mi­nal
B ... Nicht­ter­mi­nal
α, β, γ ... Kom­bi­na­tio­nen aus Ter­mi­na­len und Nicht­ter­mi­na­len
I. d. R. gilt: γ ≠ ε


Au­to­ma­ten

Gram­ma­tik:
G = (N, Σ, R, S)

End­li­cher Au­to­mat:
M = (Z, Σ, δ, S, E)

Trans­duk­tor:
M = (Z, Σ, Γ, S, δ, E, ω)

Kel­ler­au­to­mat:
M = (Z, Σ, Γ, δ, S, #, E)

Tu­ring­ma­schi­ne:
M = (Z, Σ, Γ, δ, S, #, E)

Le­gen­de:
N ... Nicht­ter­mi­na­le
Z ... Zustände
S ... Start­sym­bol bzw. Start­zu­stand/-¨e
E ... End­zustände
Σ ... (Ein­ga­be-)Al­pha­bet
Γ ... Aus­ga­be­al­pha­bet
R ... Pro­duk­ti­ons­re­geln
δ ... Überführungs­funk­ti­on
ω ... Aus­ga­be­funk­ti­on
# ... Kel­ler­sym­bol bzw. Blank-Sym­bol

G ≙ M
N ≙ Z
R ≙ δ

Kommentare:

  1. Bei der Grammatik hast du die Produktionsregeln mit "R" bezeichnet, in der Legende aber mit einem "P".

    AntwortenLöschen
    Antworten
    1. Somit setzt du "R" mit der Überführungsfunktion gleich und die Produktionsregeln P finden nirgendwo eine Verwendung.

      Löschen
    2. Danke für den Hinweis. Ich hatte wohl einmal an "Regelmenge" und einmal an "Produktionsregeln" gedacht.

      Löschen