AutoSpr - Automaten Und Sprachen an der HSR - Hochschule Für Technik Rapperswil | Karteikarten & Zusammenfassungen

Lernmaterialien für AutoSpr - Automaten und Sprachen an der HSR - Hochschule für Technik Rapperswil

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen AutoSpr - Automaten und Sprachen Kurs an der HSR - Hochschule für Technik Rapperswil zu.

TESTE DEIN WISSEN

Nennen sie zwei Methoden, mit denen Sie zeigen können das eine Sprache nicht regulär ist.

Lösung anzeigen
TESTE DEIN WISSEN
  • Pumping Lemma
  • Myhill-Nerode
Lösung ausblenden
TESTE DEIN WISSEN

Typisches Beispiel für eine nicht reguläre Sprache

Lösung anzeigen
TESTE DEIN WISSEN
  • L = {w ∈ Σ* | w ist ein Palindrom}
  • L = {0^n1^n | n ≥ 0}
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine akzeptierte Sprache eines DEA?

Lösung anzeigen
TESTE DEIN WISSEN

Die Sprache die von einem DEA akzeptiert wird ist eine reguläre Sprache.

Lösung ausblenden
TESTE DEIN WISSEN

Nennen Sie drei Methoden, mit denen Sie zeigen können, das eine Sprache regulär ist.

Lösung anzeigen
TESTE DEIN WISSEN
  • DEA konstruieren
  • NEA konstruieren
  • REGEX konstruieren 
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Sprache?

Lösung anzeigen
TESTE DEIN WISSEN
  • Wird meist bezeichnet mit L
  • Eine Sprache ist eine Teilmenge von Σ*, also L ⊂ Σ*
  • Die Sprache ist also eine Menge an Wörtern zum Alphabet Σ, welcher in einer gewissen weise Sinn ergeben

Beispiel:

Σ die Menge der ASCII-Zeichen. Σ* ist die Menge aller ASCII-Texte auch solche die keinen Sinn machen.

C = {w ∈ Σ∗ | w wird von GCC akzeptiert}.

C ist dann die Sprache im GNU-Dialekt von C.

  1.  

              

                                       

                                       

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein regulärer Ausdruck?

Lösung anzeigen
TESTE DEIN WISSEN
  • Ein regulärer Ausdruck sind Zeichenketten, die (reguläre) Sprachen beschreiben.
  • Reguläre Ausdrücke bauen reguläre Sprachen aus einzelnen Zeichen und Regulären Operationen aus 
Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein DEA?

Lösung anzeigen
TESTE DEIN WISSEN
  • Deterministischer Endlicher Automat
  • Endlich viele Zustände 
  • sieht nur ein Zeichen weit
  • kann sich nicht an ältere Zeichen erinnern
  • kann frühere Entscheidungen beim eintreffen neuer Zeichen nicht mehr revidieren
  • keine ε Übergänge

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein Alphabet?

Lösung anzeigen
TESTE DEIN WISSEN

Jede beliebige nicht leere Menge kann ein Alphabet sein.

Beispiele:                                              

Σ = {0,1}

Σ = {a,b}
                                   

Lösung ausblenden
TESTE DEIN WISSEN

Wie unterscheidet sich ein deterministischer endlicher Automat von einem nicht deterministischen endlichen Automaten?                

                                       

Lösung anzeigen
TESTE DEIN WISSEN
  • Der DEA sieht nur ein Zeichen weit, kann sich nicht an ältere Zeichen erinnern und kann frühere Entscheidungen nicht mehr revidieren
  • Der DEA lässt keine ε-Übergänge zu
  • Der DEA lässt nur einen möglichen Übergang für ein Zeichen zu


  • Ein NEA lässt mehrere Übergänge für ein Zeichen zu

  • Ein NEA lässt ε-Übergänge zu

Lösung ausblenden
TESTE DEIN WISSEN

Was ist der Unterschied zwischen ε, ∅ und {ε}?

Lösung anzeigen
TESTE DEIN WISSEN
  • ε ist das leere Wort
  • ∅ ist die leere Sprache
  • {ε}  ist die Sprache die nur das leere Enthält bezeichnet mit Σ^0
  • Die leere Sprache und die Sprache die nur das leere Wort enthält ist nicht dasselbe
Lösung ausblenden
TESTE DEIN WISSEN

Wie kann man zwei endliche Automaten vergleichen?

                                       

Lösung anzeigen
TESTE DEIN WISSEN
  1. Reduzieren der Automaten mit dem Kreuzchen-Algorithmus
    1. Wenn Automaten gleich sind akzeptieren sie die gleiche Sprache
    2. Wenn die Automaten nicht gleich sind akzeptieren sie nicht die gleiche Sprache
Lösung ausblenden
TESTE DEIN WISSEN

Beschreibe den Zusammenhang zwischen DEA's, NEA's, und regulären Ausdrücken.

Lösung anzeigen
TESTE DEIN WISSEN
  • Aus einem NEA kann immer ein DEA gemacht werden
  • Aus einem DEA kann immer ein regulärer Ausdruck gemacht werden
Lösung ausblenden
  • 5489 Karteikarten
  • 71 Studierende
  • 0 Lernmaterialien

Beispielhafte Karteikarten für deinen AutoSpr - Automaten und Sprachen Kurs an der HSR - Hochschule für Technik Rapperswil - von Kommilitonen auf StudySmarter erstellt!

Q:

Nennen sie zwei Methoden, mit denen Sie zeigen können das eine Sprache nicht regulär ist.

A:
  • Pumping Lemma
  • Myhill-Nerode
Q:

Typisches Beispiel für eine nicht reguläre Sprache

A:
  • L = {w ∈ Σ* | w ist ein Palindrom}
  • L = {0^n1^n | n ≥ 0}
Q:

Was ist eine akzeptierte Sprache eines DEA?

A:

Die Sprache die von einem DEA akzeptiert wird ist eine reguläre Sprache.

Q:

Nennen Sie drei Methoden, mit denen Sie zeigen können, das eine Sprache regulär ist.

A:
  • DEA konstruieren
  • NEA konstruieren
  • REGEX konstruieren 
Q:

Was ist eine Sprache?

A:
  • Wird meist bezeichnet mit L
  • Eine Sprache ist eine Teilmenge von Σ*, also L ⊂ Σ*
  • Die Sprache ist also eine Menge an Wörtern zum Alphabet Σ, welcher in einer gewissen weise Sinn ergeben

Beispiel:

Σ die Menge der ASCII-Zeichen. Σ* ist die Menge aller ASCII-Texte auch solche die keinen Sinn machen.

C = {w ∈ Σ∗ | w wird von GCC akzeptiert}.

C ist dann die Sprache im GNU-Dialekt von C.

  1.  

              

                                       

                                       

Mehr Karteikarten anzeigen
Q:

Was ist ein regulärer Ausdruck?

A:
  • Ein regulärer Ausdruck sind Zeichenketten, die (reguläre) Sprachen beschreiben.
  • Reguläre Ausdrücke bauen reguläre Sprachen aus einzelnen Zeichen und Regulären Operationen aus 
Q:

Was ist ein DEA?

A:
  • Deterministischer Endlicher Automat
  • Endlich viele Zustände 
  • sieht nur ein Zeichen weit
  • kann sich nicht an ältere Zeichen erinnern
  • kann frühere Entscheidungen beim eintreffen neuer Zeichen nicht mehr revidieren
  • keine ε Übergänge

Q:

Was ist ein Alphabet?

A:

Jede beliebige nicht leere Menge kann ein Alphabet sein.

Beispiele:                                              

Σ = {0,1}

Σ = {a,b}
                                   

Q:

Wie unterscheidet sich ein deterministischer endlicher Automat von einem nicht deterministischen endlichen Automaten?                

                                       

A:
  • Der DEA sieht nur ein Zeichen weit, kann sich nicht an ältere Zeichen erinnern und kann frühere Entscheidungen nicht mehr revidieren
  • Der DEA lässt keine ε-Übergänge zu
  • Der DEA lässt nur einen möglichen Übergang für ein Zeichen zu


  • Ein NEA lässt mehrere Übergänge für ein Zeichen zu

  • Ein NEA lässt ε-Übergänge zu

Q:

Was ist der Unterschied zwischen ε, ∅ und {ε}?

A:
  • ε ist das leere Wort
  • ∅ ist die leere Sprache
  • {ε}  ist die Sprache die nur das leere Enthält bezeichnet mit Σ^0
  • Die leere Sprache und die Sprache die nur das leere Wort enthält ist nicht dasselbe
Q:

Wie kann man zwei endliche Automaten vergleichen?

                                       

A:
  1. Reduzieren der Automaten mit dem Kreuzchen-Algorithmus
    1. Wenn Automaten gleich sind akzeptieren sie die gleiche Sprache
    2. Wenn die Automaten nicht gleich sind akzeptieren sie nicht die gleiche Sprache
Q:

Beschreibe den Zusammenhang zwischen DEA's, NEA's, und regulären Ausdrücken.

A:
  • Aus einem NEA kann immer ein DEA gemacht werden
  • Aus einem DEA kann immer ein regulärer Ausdruck gemacht werden
AutoSpr - Automaten und Sprachen

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten AutoSpr - Automaten und Sprachen Kurse im gesamten StudySmarter Universum

Slavische Sprachen

Universität Mainz

Zum Kurs
6. Sprache und Sprachgebrauch untersuchen

Bergische Universität Wuppertal

Zum Kurs
Sprache und Spracherwerb

University of Fribourg

Zum Kurs
Formale Sprachen und Automaten

Hochschule des Bundes für öffentliche Verwaltung

Zum Kurs
Denken und Sprache

Universität Mannheim

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden AutoSpr - Automaten und Sprachen
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen AutoSpr - Automaten und Sprachen