main idea

1. Re to NFA
2. NFA to DFA (Subset Construction Method) (也可以先NFA to NFA without $\varepsilon$)

difference between NFA and DFA

stackoverflow: DFA vs NFA engines: What is the difference in their capabilities and limitations?
DFA没有一个状态具有$\varepsilon$转换，即在输入$\varepsilon$上的转换。对每个状态$s$和输入符号$a$，DFA最多只有一条标记为$a$的边离开，即在任何状态下对任一输入符号，最多只有一个转换。

Example 1 (reference 1)

$I$中第一项其实是从state$0$，而$I_a$，$I_b$第一项开始，是从stata $0$开始，经过一个$a$所能到达的几何(可以忽略前后$\varepsilon$)。$b$同理。

Example 2 (reference 2)

(rederence 中ppt图有误。)

more example reference 3.

Reference

1. http://blog.csdn.net/qq_23100787/article/details/50402643
2. https://raphiinconcordia.files.wordpress.com/2015/05/nfa-to-dfa.ppt
3. Puntambekar A A. Formal Languages And Automata Theory[M]. Technical Publications, 2008.
4. Aho A V, 阿霍, Sethi R, et al. 编译原理[M]. 机械工业出版社, 2003.

Assignment 2:

Caesar cipher

https://en.wikipedia.org/wiki/Caesar_cipher
each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet.
encode:
$E{n}(x)=(x+n) mod 26$
decode:
$D{n}(x)=(x-n) mod 26$
Breaking the cipher:
1.an attacker knows (or guesses) that some sort of simple substitution cipher has been used, but not specifically that it is a Caesar scheme;
solution: frequency analysis or pattern words
2.an attacker knows that a Caesar cipher is in use, but does not know the shift value.
solution: brute force attack

Vigenère cipher

https://en.wikipedia.org/wiki/Vigenère_cipher
Using a series of different Caesar ciphers based on the letters of a keyword. Use the Vigenère square or Vigenère table

iloc loc

loc用index， iloc用行号

apply() applymap()

apply()用于一列或者一行
applymap()用于每一个数据