Semper Phone

Effortless
LEARNING

  • Improve effortlessly – just by living your life
  • Learn while waiting for your apps to load
  • Recommended by 5 universities
  • Community of over 1,000,000 learners
  • 50,000+ expert-made packs, or create your own
"One of the best learning apps" - CNET
  • Apple Play Store
  • Install Semper from the Play Store
Grundwissen Informatik Formale sprachen

Grundwissen Informatik Formale sprachen

Last update 

Informatik, Chomsky-Hierarchie

Items (19)

  • Die Definition vom Alphabet.

    Ist eine nicht leere Menge von Zeichen/Symbolen.

  • Die Definition von einem Wort.

    Ist eine endliche Folge aus dem Alphabet.(Symbole aneinander gehängt)

  • Was sind die Variablen einer Grammatik?

    Nicht Terminale Darstellung mit <...> oder Großbuchstaben.

  • Was sind die Zeichen/Symbole einer Sprache?

    Terminale Darstellung mit Kleinbuchstaben oder Anführungsstriche.

  • Die Definition der Grammatik.

    Besteht aus vier Komponenten G=(V,Σ,P,S)

  • Wie ist die Bedienung der Grammatik Komponenten für V?

    Ist eine endliche Menge von Nicht Terminalen. (Variablen)

  • Wie ist die Bedienung der Grammatik Komponenten für Σ?

    Ist die Menge der Terminalen.

  • Wie ist die Bedienung der Grammatik Komponenten für P?

    Ist eine endliche Menge von Produktionen. (Regeln)

  • Wie ist die Bedienung der Grammatik Komponenten für S?

    Ist die Startvariable.

  • Chomsky - Hierarchie Typ 0

    Eine Einschränkung der Produnktionsregeln.

  • Chomsky - Hierarchie Typ 1

    Die Grammatik ist kontextabhängig. Für alle Regeln l -> r gilt: |l| <= |r|.

  • Chomsky - Hierarchie Typ 2

    Die Grammatik ist kontextfrei. wenn für zusätzlich für alle l gilt das es Element von V ist.

  • Chomsky - Hierarchie Typ 3

    Die Grammatik ist regulär, wenn zusätzlich gilt das die rechte Seite von Regeln entweder einzelne Terminale oder ein Terminal gefolgt von einer Variable ist.

  • Was ist ein Automat?

    Ist eine Darstellungen von Zuständen und Übergängen zwischen diesen Zuständen. (gerichteter Graph)

  • Wann ist ein Automat äquivalent?

    Wenn beide dieselbe Sprache akzeptieren.

  • Was ist ein Minimalautomat?

    Es besitzt die geringstmögliche Anzahl von Zuständen.

  • Wie kann man einen Minimalautomaten bestimmen mit einer Menge äquivalenten Automaten?

    Alle nicht erreichbaren Zuständen entfernen und Zustände Zusammenfassen die die Sprache nicht ändern.

  • DEA

    deterministischer endlicher Automat

  • NEA

    nichtdeterministischer endlicher Automat