Knowunity
Schule. Endlich einfach.
Automaten, Grammatiken und Verschlüsselung
Jule
42 Followers
Teilen
Speichern
17
12/13
Lernzettel
Endliche Automaten (DEA, NEA, Moore, Mealy), Beschreibung regulärer Sprachen durch Grammatiken, Binärbäume (Aufbau und Travesierung), Hamming-Distanz, Huffman-Codierung, Verschlüsselung (Caeser und Vigenere (Häufigkeitsanalyse, Kasizki-Test).
4) Endliche Automaten al deterministische Automaten DEA eindeutiger zustand, da eine Eingabe nur zu einer Ausgabe führen kann. b) nicht deterministische Automaten NEA → mehrere Pfeile mit gleicher Beschriftung möglich -。 leere übergänge DEA-übergangstabelle binga .. 7, Z₂ Z₁ Zo Z₂ Z; Z₁ 근 Zo 2₂ a b • babba c) Mealy - Maschine → endlicher Automat mit Ausgabe Ausgabe 0/1 Knoten 10. 5 15 5 mögliche Ausgaben dieses Automaten: • abbaa 1/0 Z₂ d) Moore- Maschine 21/0 4 5 6 7 20. Z₁ 20 0/0 23 (8) Binārbaume Aufbau: a.c 30 25 35 Ausgabe: 20 10 5 15 Das PostOrder-Verfahren: Binar-Code 000 001 b 010 0 11 100 101 110 1 11 Q Eingabe Folgezusland Ausgabe 0 Zo 1 1 Zo Zo b z. Z₂ Z₂ ... Wurzel (0) 1 10. 30 1. Linker Teilbaum 2 rechter Teilbaum 15 25 35 3. Wurzel Ausgabe: 5 15 10 25 30 35 20 1 2 (9) Hamming- Distanz Dezimal- zahl 0 1 2 3 1 2 2 3 0 kante 1 0 1 Abstand zu 000 Z₁ Z₂ Zo 888 Travesierung die Ausgabe des Binàrbaums als Text Das Pre Order-Verfahren: Blatt Zo Z₂ →die Ausgabe ist nicht von dem übergang abhängig, sondern von dem ausgehenden Zustand! 1. Wurzel 2. linker Teilbaum 3. rechter Teilbaum 30 25 35 4) Beschreibung regulärer Sprachen durch Grammatiken N = (B₁C₁D₁S) Variablen T = (a, b, c) Terminale (.Ausgaben) Beispiel: N= (S. A, B) T= (9. 0₁ 1₁ +₁ *) S 9 10 11 1 AQ IBO IB₁ A S+ W₁ = a B S* W₂ = Aa + S+a → ₁+a W3 =B₁ S*1 → Aa* 1 → Sta* ₁ →→ 0+ a² 1 G Zo تم له ته Z₁ Z₂ 0 0 1 1 0 Grad 3 Grad O a Z3 Grad 2 Z₂ Za 5 Eingabe/Ausgabe kein Endzustand Po 10. 15 Ausgabe: 5 20 d₁ b ZA Das In Order-Verfahren: ZA Zn Z₂ do 03 9,0,1 Grad 3 P₂ 9. C Zz Z₂ \ РА 8 dz A Z₁ 1 92 NON 2 91 30 25 35 10 15 20 25 30 35 Grad 1 do da 1 1 1 000 200 0=44 R=1 O 1 Ils 1 1 Olz d3 0 1 0 0 1 1 1 1 1 4/13 4/13 1/13 1/13 0 0 0 Die Überprüfung des Hamming-Codes (der empfangen wurde) erfolgt mittels der Berechnung des Syndroms: So= po alt + Ponen S₁ = P₁ 2²6 + Pa neu 8₂= P₂ alt + P₂ new mit dem Beispiel: So = 0...
App herunterladen
+ 1 = 1 S₁ = 0 + 1 S₂ = 1 + 0 1/13 1/13 0 (10) Huffman - Codierung Bsp.: Anzahl von ^' - gerade ~0. Anzani von.1 = ungerade 1 Po= do dnd3 = 101 0 P₁= do d₂ d3 = 101 0 1 P₂= dn d₂ ds = 001 } 1 po= do dnd3= 010 → P₁= do d₂ d3 = 010 1 P₂= da d₂ d3 = 110 → 0 KROKODIL KOKO → 13 insgesamt wenn fehlerlos: So 0 S₁₂ = 0 S₂ = 0 1 + 08/13. D + 1 2/13 D+ 1 + R = 3/137 L + ' 2/13 1/13 CodeWorter: K 11 Speicherbere chnung an diesem Beispiel: Huffman: verfahren: (po pn do pz dn dz 03) 10010011001 0110 1100 110 D+1+R+L+" 5/13 2.2 Bits + 3. 3 Bits + 2.4 Bits = 21 Bits ASCII: 13 & Bits = 104 Bits (11) verschlüsselung d) caesar- verschlüsselung 0 10 R010 D0111 10110 verschlüsselen Text N entsprechen → Schlüsselzahi bestimmen Grundlagen der ver- und Entschlüsselung: Bsp.: verschlüsseln von W Sz:5 Entschlüsseln von B Sz: 5 Angriff: → Häufigkeitsanalyse Effiziens: Einfach zu ver- und Ent- schlüsseln - auch von Außen! e) vigenere - verschlüsselung - Poly- alphabetische verschlüsselung Grundlagen zur ver- und Entschlus- selung Bsp.: Verschlüsselung von F' mit E (F + bis E bis Geheimtext = GT+z) Entschlüsselung von Z mit. E (Zbis. E 4 bis klartext = KTOF) (So. S₁, S₂)=> Syndrom 91₁ > 11 L R 4 0/1 ID L001 · Monoalphabetische verschlüsselung Häufigkeitsanalyse →Suche nach den häufigsten Buchstaben im diese sollten (in DE) den Buchstaben E und O 1. Linker Teilbaum 2. Wurzel 3. rechter Teilbaum Effiziens - Quasi Caeser mit anderen Schlüsselzahlen. Lässt Sich relativ einfach und schnell entschlüsseln Angriff Kasizki - Test -Suche nach wiederholungen (XWXK oder KOAC) wje kürzer die Wiederholungen, desto eher ist es Zufall -Abstand zwischen solchen Wiederholungen zählen XWXK AJ M M L Q 6 XWXK und KOAC LMG B G J W 16 Zeichen 36 zeichen -kleinster Gemeinsamer Teiler → Schlüsselwortlänge von (4) K "000 (W+ 5 SP = GT → B) (5 bis.B 4 Bis Sz=0=KTOW) KOAC
Automaten, Grammatiken und Verschlüsselung
Jule •
Follow
42 Followers
Endliche Automaten (DEA, NEA, Moore, Mealy), Beschreibung regulärer Sprachen durch Grammatiken, Binärbäume (Aufbau und Travesierung), Hamming-Distanz, Huffman-Codierung, Verschlüsselung (Caeser und Vigenere (Häufigkeitsanalyse, Kasizki-Test).
2
Von Neumann Prinzip
1
11/12/13
2
Caesar-Verschlüsselung
31
11
2
Automaten und Grammatiken Abi 2022
25
13
Automaten: bearbeitete Übungen die Automaten erklären
24
11/12
4) Endliche Automaten al deterministische Automaten DEA eindeutiger zustand, da eine Eingabe nur zu einer Ausgabe führen kann. b) nicht deterministische Automaten NEA → mehrere Pfeile mit gleicher Beschriftung möglich -。 leere übergänge DEA-übergangstabelle binga .. 7, Z₂ Z₁ Zo Z₂ Z; Z₁ 근 Zo 2₂ a b • babba c) Mealy - Maschine → endlicher Automat mit Ausgabe Ausgabe 0/1 Knoten 10. 5 15 5 mögliche Ausgaben dieses Automaten: • abbaa 1/0 Z₂ d) Moore- Maschine 21/0 4 5 6 7 20. Z₁ 20 0/0 23 (8) Binārbaume Aufbau: a.c 30 25 35 Ausgabe: 20 10 5 15 Das PostOrder-Verfahren: Binar-Code 000 001 b 010 0 11 100 101 110 1 11 Q Eingabe Folgezusland Ausgabe 0 Zo 1 1 Zo Zo b z. Z₂ Z₂ ... Wurzel (0) 1 10. 30 1. Linker Teilbaum 2 rechter Teilbaum 15 25 35 3. Wurzel Ausgabe: 5 15 10 25 30 35 20 1 2 (9) Hamming- Distanz Dezimal- zahl 0 1 2 3 1 2 2 3 0 kante 1 0 1 Abstand zu 000 Z₁ Z₂ Zo 888 Travesierung die Ausgabe des Binàrbaums als Text Das Pre Order-Verfahren: Blatt Zo Z₂ →die Ausgabe ist nicht von dem übergang abhängig, sondern von dem ausgehenden Zustand! 1. Wurzel 2. linker Teilbaum 3. rechter Teilbaum 30 25 35 4) Beschreibung regulärer Sprachen durch Grammatiken N = (B₁C₁D₁S) Variablen T = (a, b, c) Terminale (.Ausgaben) Beispiel: N= (S. A, B) T= (9. 0₁ 1₁ +₁ *) S 9 10 11 1 AQ IBO IB₁ A S+ W₁ = a B S* W₂ = Aa + S+a → ₁+a W3 =B₁ S*1 → Aa* 1 → Sta* ₁ →→ 0+ a² 1 G Zo تم له ته Z₁ Z₂ 0 0 1 1 0 Grad 3 Grad O a Z3 Grad 2 Z₂ Za 5 Eingabe/Ausgabe kein Endzustand Po 10. 15 Ausgabe: 5 20 d₁ b ZA Das In Order-Verfahren: ZA Zn Z₂ do 03 9,0,1 Grad 3 P₂ 9. C Zz Z₂ \ РА 8 dz A Z₁ 1 92 NON 2 91 30 25 35 10 15 20 25 30 35 Grad 1 do da 1 1 1 000 200 0=44 R=1 O 1 Ils 1 1 Olz d3 0 1 0 0 1 1 1 1 1 4/13 4/13 1/13 1/13 0 0 0 Die Überprüfung des Hamming-Codes (der empfangen wurde) erfolgt mittels der Berechnung des Syndroms: So= po alt + Ponen S₁ = P₁ 2²6 + Pa neu 8₂= P₂ alt + P₂ new mit dem Beispiel: So = 0...
App herunterladen
Knowunity
Schule. Endlich einfach.
+ 1 = 1 S₁ = 0 + 1 S₂ = 1 + 0 1/13 1/13 0 (10) Huffman - Codierung Bsp.: Anzahl von ^' - gerade ~0. Anzani von.1 = ungerade 1 Po= do dnd3 = 101 0 P₁= do d₂ d3 = 101 0 1 P₂= dn d₂ ds = 001 } 1 po= do dnd3= 010 → P₁= do d₂ d3 = 010 1 P₂= da d₂ d3 = 110 → 0 KROKODIL KOKO → 13 insgesamt wenn fehlerlos: So 0 S₁₂ = 0 S₂ = 0 1 + 08/13. D + 1 2/13 D+ 1 + R = 3/137 L + ' 2/13 1/13 CodeWorter: K 11 Speicherbere chnung an diesem Beispiel: Huffman: verfahren: (po pn do pz dn dz 03) 10010011001 0110 1100 110 D+1+R+L+" 5/13 2.2 Bits + 3. 3 Bits + 2.4 Bits = 21 Bits ASCII: 13 & Bits = 104 Bits (11) verschlüsselung d) caesar- verschlüsselung 0 10 R010 D0111 10110 verschlüsselen Text N entsprechen → Schlüsselzahi bestimmen Grundlagen der ver- und Entschlüsselung: Bsp.: verschlüsseln von W Sz:5 Entschlüsseln von B Sz: 5 Angriff: → Häufigkeitsanalyse Effiziens: Einfach zu ver- und Ent- schlüsseln - auch von Außen! e) vigenere - verschlüsselung - Poly- alphabetische verschlüsselung Grundlagen zur ver- und Entschlus- selung Bsp.: Verschlüsselung von F' mit E (F + bis E bis Geheimtext = GT+z) Entschlüsselung von Z mit. E (Zbis. E 4 bis klartext = KTOF) (So. S₁, S₂)=> Syndrom 91₁ > 11 L R 4 0/1 ID L001 · Monoalphabetische verschlüsselung Häufigkeitsanalyse →Suche nach den häufigsten Buchstaben im diese sollten (in DE) den Buchstaben E und O 1. Linker Teilbaum 2. Wurzel 3. rechter Teilbaum Effiziens - Quasi Caeser mit anderen Schlüsselzahlen. Lässt Sich relativ einfach und schnell entschlüsseln Angriff Kasizki - Test -Suche nach wiederholungen (XWXK oder KOAC) wje kürzer die Wiederholungen, desto eher ist es Zufall -Abstand zwischen solchen Wiederholungen zählen XWXK AJ M M L Q 6 XWXK und KOAC LMG B G J W 16 Zeichen 36 zeichen -kleinster Gemeinsamer Teiler → Schlüsselwortlänge von (4) K "000 (W+ 5 SP = GT → B) (5 bis.B 4 Bis Sz=0=KTOW) KOAC