---
layout  : wiki
title   : 형식언어와 오토마타.02.04
summary : REDUCTION OF THE NUMBER OF STATES IN FINITE AUTOMATA
date    : 2018-12-19 21:00:35 +0900
updated : 2018-12-19 21:07:05 +0900
tags    : cs
toc     : true
public  : true
parent  : study-formal-languages-and-automata
latex   : true
---
* TOC
{:toc}

* CHAPTER 2. Finite Automata
    * [2.1 DETERMINISTIC FINITE ACCEPTERS](/wiki/f-l-a-02-01)
    * [2.2 NONDETERMINISTIC FINITE ACCEPTERS](/wiki/f-l-a-02-02)
    * [2.3 EQUIVALENCE OF DETERMINISTIC AND NONDETERMINISTIC FINITE ACCEPTERS](/wiki/f-l-a-02-03)
    * **2.4 REDUCTION OF THE NUMBER OF STATES IN FINITE AUTOMATA**
* 챕터 2. 유한 오토마타
    * 2.1 결정적 유한 인식기
    * 2.2 비결정적 유한 인식기
    * 2.3 결정적 유한 인식기와 비결정적 유한 인식기의 동치성
    * **2.4 유한 오토마타에서의 상태의 수 축소**

# 공간 효율이 좋은 오토마타가 더 바람직하다

* 한 dfa는 한 언어를 정의한다.
* 그러나 한 언어를 정의하는 dfa는 여러 개 있을 수 있다.
* 공간 효율을 위해 여러 dfa 중에서 상태가 적은 오토마타를 선택하는 것이 바람직하다.

>
DEFINITION 2.8  
Two states p and q of a dfa are called indistinguishable if  
$$δ* (p, w) ∈ F implies δ* (q, w) ∈ F$$,  
and  
$$δ* (p, w) ∉ F implies δ* (q, w) ∉ F$$,  
for all w ∈ Σ*. If, on the other hand, there exists some string w ∈ Σ* such that  
$$δ* (p, w) ∈ F and δ* (q, w) ∉ F$$,  
or vice versa, then the states p and q are said to be distinguishable by a string w.

Add 유한 오토마타에서의 상태의 수 축소
Add 유한 오토마타에서의 상태의 수 축소
