[컴퓨테이션이론] ch1. Convert NFA to DFA (2)

Regular language <-> DFA & NFA

A language is regular <=> if some nondeterministic finite automaton recognizes it

-> : Because a regular language has a DFA recognizing it and any DFA is also an NFA

<- : If an NFA recognizes some language, so does some DFA, and hence the language is regular

Convert NFA to DFA example (2)

 

DFA (NFA 변환함)

MINIMIZE 해서 표현 할 수도 (안 중요)

---

Union (NFA로 증명-저번엔 DFA로 증명함)

간단한 Proof idea

proof

---

Concatenation (NFA로 증명-저번엔 DFA로 증명함)

간단한 proof idea

proof

---

Closure under start Operation  (NFA로 증명-저번엔 DFA로 증명함)

간단한 proof idea