Editing TU Wien:Theoretische Informatik und Logik VU (Fermüller, Oswald)/Zusammenfassung BFSK

Jump to navigation Jump to search

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision Your text
Line 1: Line 1:
 
[[Kategorie:Wikitext-Zusammenfassungen]]
 
[[Kategorie:Wikitext-Zusammenfassungen]]
 
Diese Seite fasst den Stoff von Teil 1: ''Berechenbarkeit, Formale Sprachen und Komplexitätstheorie'' (BFSK) zusammen.
 
Diese Seite fasst den Stoff von Teil 1: ''Berechenbarkeit, Formale Sprachen und Komplexitätstheorie'' (BFSK) zusammen.
 
{| class=wikitable
 
! Sprachfamilie !! Grammatiktyp !! Maschinenmodell
 
|-
 
| [[#rekursiv aufzählbar|rekursiv aufzählbar]] || Typ-0: [[#Grammatiken|unbeschränkte Grammatik]] || Turingmaschine (EA + RAM)
 
|-
 
| kontextsensitiv || Typ-1: kontextsensitiv, monoton || linear beschränkter Automat (EA + beschr. RAM)
 
|-
 
| kontextfrei || Typ-2: [[#Kontextfreie Grammatiken|kontextfreie Grammatik]] || Kellerautomat (EA + Stack)
 
|-
 
| [[#Reguläre Sprachen|regulär]] || Typ-3: [[#Reguläre Grammatiken|reguläre Grammatik]] || endlicher Automat (EA)
 
|}
 
  
 
== Formale Sprachen ==
 
== Formale Sprachen ==
Line 57: Line 45:
 
== Reguläre Sprachen ==
 
== Reguläre Sprachen ==
  
Werden von '''endlichen Automaten''' akzeptiert und von [[#Reguläre Grammatiken]] erzeugt.
+
Eine formale Sprache heißt regulär, wenn sie von einem '''endlichen Automaten''' akzeptiert wird.
  
 
=== Pumping Lemma ===
 
=== Pumping Lemma ===
Line 101: Line 89:
 
* <math>F \subseteq Q</math> Menge der Endzustände
 
* <math>F \subseteq Q</math> Menge der Endzustände
  
;Akzeptierte Sprache <math>L(M)</math>
+
== Akzeptierte Sprache ==
:Besteht aus genau all jenen Wörtern, bei deren Analyse M einen Endzustand erreicht.
+
 
;Rekursiv aufzählbare Sprachen{{anchor|rekursiv aufzählbar}}
+
Die von der Turingmaschine M akzeptierte Sprache <math>L(M)</math> besteht aus genau all jenen Wörtern, bei deren Analyse M einen Endzustand erreicht.
 +
 
 +
;Rekursiv aufzählbare Sprachen
 
:Es gibt eine TM, welche die Sprache akzeptiert, aber bei <math>w \notin L</math> unter Umständen unendlich läuft.
 
:Es gibt eine TM, welche die Sprache akzeptiert, aber bei <math>w \notin L</math> unter Umständen unendlich läuft.
 
;Rekursive Sprachen
 
;Rekursive Sprachen
Line 123: Line 113:
 
* B rekursiv aufzählbar &rarr; A rekursiv aufzählbar
 
* B rekursiv aufzählbar &rarr; A rekursiv aufzählbar
  
Eine '''Eigenschaft''' von Sprachen ist eine Teilmenge P von rekursiv aufzählbaren Sprachen (über einem geeigneten Alphabet).
+
;triviale Eigenschaft
 
+
:Ist entweder leer oder besteht aus allen rekursiv aufzählbaren Sprachen.
Eine Eigenschaft ist '''trivial''', wenn sie entweder leer ist, oder aus allen rekursiv aufzählbaren Sprachen besteht. Andernfalls ist sie nicht trivial.
 
 
 
 
;Satz von Rice
 
;Satz von Rice
 
:Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar.
 
:Jede nicht triviale Eigenschaft der rekursiv aufzählbaren Sprachen ist unentscheidbar.
Line 143: Line 131:
 
* <math>P \subseteq (N \cup T)^+ \times (N \cup T)^*</math> ... Produktionen
 
* <math>P \subseteq (N \cup T)^+ \times (N \cup T)^*</math> ... Produktionen
 
* <math>S \in N</math> ... Startsymbol
 
* <math>S \in N</math> ... Startsymbol
 
Jede Grammatik dieser Form heißt '''unbeschränkte Grammatik'''. Gilt für alle Produktionen <math>\alpha \to \beta \in P</math>:
 
 
* <math>|\alpha| \leq |\beta|</math> so heißt G '''monoton'''
 
* <math>\alpha = uAv</math> und <math>\beta = uwv</math> für ein <math>A \in N, w \in (N \cup T)^+</math> und <math>u,v \in (N \cup T)^*</math> so heißt G '''kontextsensitiv'''.
 
* <math>A \to \beta</math> für ein <math>A \in N</math>, so heißt G [[#Kontextfreie Grammatiken|kontextfrei]].
 
* <math>A \to aB</math> oder <math>A \to \epsilon</math>, so heißt G [[#Reguläre Grammatiken|regulär]].
 
  
 
Wörter, die nur aus Terminalsymbolen bestehen, werden Satzformen genannt.
 
Wörter, die nur aus Terminalsymbolen bestehen, werden Satzformen genannt.
Line 170: Line 151:
 
|}
 
|}
  
=== Reguläre Grammatiken ===
+
=== Typ-3: Reguläre Grammatiken ===
  
 
Alle Produktionen sind von der Form <math>A \to aB</math> oder <math>A \to \epsilon</math>.
 
Alle Produktionen sind von der Form <math>A \to aB</math> oder <math>A \to \epsilon</math>.
  
Alternativ:
+
=== Typ-2: Kontextfreie Grammatiken ===
 
 
Alle Produktionen sind von der Form <math>A \to aB</math> oder <math>A \to a</math>.
 
<math>S \to \epsilon</math> ist erlaubt, sofern S nicht auf einer rechten Seite vorkommt.
 
 
 
;Beispiele
 
 
 
* <math>L = \{a\}^* = \{ a^n \mid n \geq 0\}</math>
 
: <math>G = (\{S\}, \{a\}, \{S \to aS \mid \epsilon\}, S)</math>
 
* <math>L = \{a\}^+ = \{ a^n \mid n \geq 1\}</math>
 
: <math>G = (\{S\}, \{a\}, \{S \to aS \mid a\}, S)</math>
 
 
 
=== Kontextfreie Grammatiken ===
 
  
 
* Linksableitung &mdash; es wird immer das erste Nonterminal ersetzt
 
* Linksableitung &mdash; es wird immer das erste Nonterminal ersetzt
Line 207: Line 176:
 
* Schnitt mit regulären Sprachen
 
* Schnitt mit regulären Sprachen
  
==== Beispiele ====
+
==== Dyck-Sprachen ====
  
;Dyck-Sprachen
 
 
<math>D_n</math> ist die Wortmenge der wohlgeformten Klammerausdrücke mit <math>n</math> unterschiedlichen Klammerpaaren. ([[de.wikipedia:Dyck-Sprache|Wikipedia]])
 
<math>D_n</math> ist die Wortmenge der wohlgeformten Klammerausdrücke mit <math>n</math> unterschiedlichen Klammerpaaren. ([[de.wikipedia:Dyck-Sprache|Wikipedia]])
  

Please note that all contributions to VoWi are considered to be released under the GNU Free Documentation License 1.3 (see VoWi:Urheberrechte for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel Editing help (opens in new window)

Template used on this page: