TechCodeview

• DFA는 결정론적 유한 오토마타를 의미합니다. 결정론적이란 계산의 고유성을 나타냅니다. 기계가 입력 문자열을 한 번에 한 기호씩 읽는 경우 유한 오토마타를 결정론적 유한 오토마타라고 합니다.
• DFA에는 현재 상태에서 다음 상태로의 특정 입력에 대한 경로가 하나만 있습니다.
• DFA는 null 이동을 허용하지 않습니다. 즉, DFA는 입력 문자 없이 상태를 변경할 수 없습니다.
• DFA에는 여러 최종 상태가 포함될 수 있습니다. 컴파일러의 어휘 분석에 사용됩니다.

다음 다이어그램에서는 입력 a에 대한 상태 q0에서 q1로 가는 경로가 하나만 있음을 알 수 있습니다. 마찬가지로, q0에서 q2로 가는 입력 b의 경로는 단 하나뿐입니다.

DFA의 공식적인 정의

DFA는 FA 정의에서 설명한 것과 동일한 5-튜플의 모음입니다.

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

전환 함수는 다음과 같이 정의할 수 있습니다.

 δ: Q x ∑→Q 

DFA의 그래픽 표현

DFA는 상태 다이어그램이라는 이중 그래프로 표현될 수 있습니다. 그 내용은 다음과 같습니다.

1. 상태는 정점으로 표현됩니다.
2. 입력 문자로 표시된 호는 전환을 나타냅니다.
3. 초기 상태는 화살표로 표시됩니다.
4. 최종 상태는 이중 원으로 표시됩니다.

예시 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

해결책:

전환 다이어그램:

전환 테이블:

예 2:

∑ = {0, 1}인 DFA는 0으로 시작하는 모든 것을 허용합니다.

해결책:

설명:

• 위 다이어그램에서 상태 q0의 DFA에 대한 입력으로 주어진 0에서 DFA는 상태를 q1로 변경하고 입력 0 시작 시 항상 최종 상태 q1로 이동하는 것을 볼 수 있습니다. 00, 01, 000, 001...을 받아들일 수 있습니다. .등. 1로 시작하는 문자열에서는 최종 상태로 전환되지 않으므로 1로 시작하는 문자열은 허용되지 않습니다.

예시 3:

∑ = {0, 1}인 DFA는 0으로 끝나는 모든 것을 허용합니다.

해결책:

설명:

위 다이어그램에서 상태 q0의 DFA에 대한 입력으로 주어진 0에서 DFA가 상태를 q1로 변경하는 것을 볼 수 있습니다. 00, 10, 110, 100... 등과 같이 0으로 끝나는 모든 문자열을 허용할 수 있습니다. 1로 끝나는 문자열은 허용되지 않습니다. 왜냐하면 1개의 입력에서 최종 상태 q1로 절대 이동하지 않기 때문입니다. 따라서 1로 끝나는 문자열은 허용되지 않거나 거부됩니다.