암호학 - 5주차 2차시
DFA cannot solve L5
- How do you know? Intuition First
Proof using Pumping Lemma
- Assume a DFA M accepts L5 , M has n states for some n
- Important Note : One single "Finite" Machine should accept all string in L5
- Think about \(0^{n}1^{n}\)
Pumping Lemma in Regular Language
Pumping Lemma란 Language가 DFA로 표현될 수 없음을 증명하기 위해 사용되는 것이다.
https://www.youtube.com/watch?v=Ow-gfFkXPZw
https://www.youtube.com/watch?v=dikEDuepOtI
-DFA가 L5를 못푼다.
L5={ x | x = \(0^{i}1^{i}\) for some i\(\geq\)0)}
-Think about \(0^{n}1^{n}\)
위를 DFA로 표현할 수 있는가?
-> Pumping Lemma를 이용해서 증명해보자
https://www.youtube.com/watch?v=vcND4aGPWtM
https://www.youtube.com/watch?v=5GG8goBW9gw
Questions
- How Many Strings are there?
- How Many Problems are there?
- How Many Solutions are there?
- Some Problems are Unsolvable, actually Most Problems are Unsolvable
- How Many Describable Problems are there?
Answers
1. How Many Strings are there?
-> Countably Infinite
2. How Many Problems are there?
->\(2^{\Sigma ^{\ast }}\)
\(\Sigma ^{\ast }\): 모든 가능한 string의 set
모든 가능한 string set의 부분집합
cf) \(\Sigma ^{\ast }\)는 모든 가능한 string의 집합이니까
Problem, Language이며 \(\Sigma ^{\ast }\)에 해당하는 문제는 모든 입력에 대해 답이 yes인 문제
3. How Many Solutions are there?
->Countable
Description = Finite String
설명이 됐다는 것은 유한한 문자열이다.
Classes
- Class : Set of Problems (Usually sharing some properties)
- How many Classes are there?
- How many Describable Classes are there?
1. How many Classes are there?
-> \(2^{2^{\Sigma ^{\ast }}}\)
2. How many Describable Classes are there?
-> Countable
Class DFA
- Class DFA : Set of Languages that can be solved by a DFA
NFA
- NFA : Nondeterminstic Finite Automata
- NFA : M = (Q, \(\sum\), q , F, s)
- Q : Set of states
- \(\sum\) : Set of Tape Symbols
- q : Initial State
- F : Set of Final States
- s : Transition Relation
- From (q,a) to r
- q,r:States
- a:Symbol
- There can be many r's for one (q,a) or none
Acceptance by NFA
- NFA may have different results for the same input
- according to which of the transitions to follow
- NFA M accepts input x if there exists at least one execution
where M results in a final state - Note that this definition is NOT Symmetric between Yes and No
DFA for X3
- Problem X3: 입력에 101이 있는가?
- L3 = {101, 0101, 01010, 1101, 1101111, ...}
Why use NFA?
- Simulating NFA is expensive
- But NFA is easier for thinking
- (Classes) DFA = NFA
- Why?
Can Some Machine Accept L5?
- L5={ x | x = \(0^{i}1^{i}\) for some i\(\geq\)0)}
- The Pushdown Automata (DPDA)
- DPDA can accept L6= { x | x = y2 \(y^{R}\) , y \(\end{aligned}\) \(\left\{ 0,1\right\} ^{\ast }\) }
DPDA in Action
- DPDA can accept L6 = { x | x = y2\(yR\), y \(\end{aligned}\) \(\left\{ 0,1\right\} ^{\ast }\) }
https://www.youtube.com/watch?v=7tRjX0VHHZg
https://www.youtube.com/watch?v=fYwEUXLBUdU
https://www.youtube.com/watch?v=fYwEUXLBUdU
https://www.youtube.com/watch?v=Z17j_AZwuug&t=114s