Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Sprache

Typ-3-sprachen


1. Java
2. Viren



Dies sind Sprachen, die durch Typ-3-Grammatiken definiert werden.



5.1 Reguläre Grammatik



Dies ist eine kontextfreie Grammatik, die dadurch eingeschränkt wird, daß auf der rechten Seite jeder Regel neben terminalen Symbolen höchstens ein nichtterminales Symbol steht. Tritt auf der rechten Seite ein Nichtterminal auf, so muß es für alle Produktionsregeln einheitlich nur ganz rechts oder nur ganz links stehen:




\"u ® v aus P gilt: u Î N und v Î T* o N oder v Î T* (v ¹ e) (rechtslinear)


\"u ® v aus P gilt: u Î N und v Î N o T* oder v Î T* (v ¹ e) (linkslinear)



Dabei bedeutet o das Konkatenationszeichen. Das bislang verwendete Verbundzeichen È kann nicht eingesetzt werden, da es hier auf die genaue Reihenfolge ankommt und der Verbund von Mengen kommutativ ist.



Zulässig: A ® aaB, B ® b

Verboten: A ® aBa, C ® e



5.2 Beispiel

G = (T, N, P, S)

T = {X0, X1}

N = {a, b},

S= X0

P= {X0 ® X0b, X0 ® X1b, X1 ® X1a, X1 ® a}

Die von G erzeugte Sprache ist L(G) = {aibk | i, k > 0}


Bsp.:

X0 ® X0b ® X1bb ® X1abb ® aabb




5.3 Endlicher Automat

Endliche Automaten nutzen Sprachen des Typs 3.

Definition: Ein endlicher Automat ist ein Sechstupel A = (I, O, Q, δ, q0, F), wobei

- I ist das Eingabealphabet (alle gültigen Eingabezeichen, die der Automat kennt),

- O ist das Ausgabealphabet (analog zu I),

- Q ist eine endliche, nichtleere Menge von Zuständen,


- q0 Î Q der Startzustand,

- δ: Q x I → Q x O die Zustandsübergangsfunktion mit einer Abbildung der Paare (q, i), wobei q Î Q ein Zustand ist und i Î I ein Eingabezeichen in ein Paar (q\', o), wobei q\' Î Q ein Folgezustand und o Î O ein Ausgabezeichen ist sowie

- F Í Q der Menge der Endzustände.


Anmerkung:

Die einzelnen hier aufgeführten Typen werden in den meisten Literaturquellen als Chomskytypen bezeichnet. Dies entspricht auch der Richtigkeit, jedoch habe ich hier aufgrund der Einfachheit das Chomsky weggelassen.

Noch kurz zur Sprache in diesem Zusammenhang. Eine Sprache L Í T* ist von Chomsky-Typ-i(i=0,1,2,3), falls eine Chomsky-Grammatik G von diesem Typ i existiert, die diese Sprache erzeugt L = L(G). Die gängigen Programmiersprachen sind alle kontextfreie Sprachen (der Wichtigkeit und Vollständigkeit halber noch einmal).

Um bei der Vervollständigung zu bleiben. Die Vollständigkeit erlangt Chomsky-Lehre(Hierarchie), indem algorithmische Sprachklassen(Entscheidbarkeit) und die Klassen akzeptierender Automaten eingeordnet werden:


- aufzählbare Sprachen


- entscheidbare Sprachen


- reguläre Sprachen

(siehe 1)
5

 
 




Datenschutz

Top Themen / Analyse
Hashing -
Das WAN-Netzwerk
Adressierung einer e-mail:
Bestandteile eines Prozessors
IBM baut schnellsten Supercomputer
Das uncommited dependency Problem
Grundlagen der Datenübertragung
Die AND, OR, XOR und NOT - Befehle
Was ist eigentlich ein Programm?
Interpolation -





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.