FA(Finite Automata)는 패턴을 인식하는 가장 간단한 기계입니다. 이는 정규 언어를 특성화하는 데 사용됩니다(예: /baa+!/).
또한 자연어 표현을 분석하고 인식하는 데에도 사용됩니다. 유한 오토마타 또는 유한 상태 기계는 5개의 요소 또는 튜플을 가진 추상 기계입니다. 한 상태에서 다른 상태로 이동하기 위한 일련의 상태와 규칙이 있지만 적용되는 입력 기호에 따라 다릅니다. 상태와 규칙 집합에 따라 입력 문자열이 승인되거나 거부될 수 있습니다. 기본적으로 입력 문자열을 읽고 현재 입력 기호에 따라 내부 상태를 변경하는 디지털 컴퓨터의 추상 모델입니다. 모든 자동 장치는 언어, 즉 허용되는 문자열 집합을 정의합니다. 다음 그림은 일반 자동화의 몇 가지 필수 기능을 보여줍니다.

정렬된 배열 목록 자바

수치: 유한 오토마타의 특징

위 그림은 오토마타의 다음 기능을 보여줍니다.

1. 입력
2. 산출
3. 오토마타의 상태
4. 상태 관계
5. 출력관계

유한 오토마타는 다음으로 구성됩니다.

Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>

기계의 정식 사양은 다음과 같습니다.

{ Q, ?, q, F, ? }>

FA는 두 가지 유형으로 분류됩니다.

1) 결정론적 유한 오토마타(DFA):

DFA consists of 5 tuples {Q, ?, q, F, ?}. Q : set of all states. ? : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. ? : Transition Function, defined as ? : Q X ? -->Q.>

DFA에서는 특정 입력 문자에 대해 기계가 한 가지 상태로만 전환됩니다. 모든 입력 기호의 모든 상태에 대해 전이 함수가 정의됩니다. 또한 DFA null(또는 ?) 이동은 허용되지 않습니다. 즉, DFA는 입력 문자 없이 상태를 변경할 수 없습니다.

예를 들어 'a'로 끝나는 모든 문자열의 언어를 허용하는 DFA를 구성합니다.
주어진 : ? = {a,b}, q = {q₀}, F={q₁}, Q = {q₀, q₁}

먼저, 정확한 상태 전이 다이어그램을 구성하기 위해 가능한 모든 허용 가능한 문자열의 언어 세트를 고려하십시오.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, 아버지, 아버지, 아버지, 아버지}
위는 허용 가능한 문자열의 간단한 하위 집합입니다. 'a'로 끝나고 기호 {a,b}를 포함하는 다른 많은 문자열이 있을 수 있습니다.

그림 1. ?가 포함된 DFA의 상태 전이 다이어그램 = {a, b}

허용되지 않는 문자열은 다음과 같습니다.
ab, bb, aab, abbb 등.

위의 자동장치에 대한 상태 전이 테이블,

한 가지 중요한 점은, 하나의 패턴에 대해 가능한 DFA가 많을 수 있습니다. . 일반적으로 최소한의 상태를 갖는 DFA가 선호됩니다.

2) 비결정론적 유한 오토마타(NFA): NFA는 다음 추가 기능을 제외하고 DFA와 유사합니다.

1. Null(또는 ?) 이동이 허용됩니다. 즉, 기호를 읽지 않고도 앞으로 이동할 수 있습니다.
2. 특정 입력에 대해 여러 상태로 전송하는 기능.

그러나 위의 기능은 NFA에 어떤 기능도 추가하지 않습니다. 둘 다 전력 측면에서 비교하면 둘 다 동일합니다.

위의 추가 기능으로 인해 NFA에는 전환 기능이 다르며 나머지는 DFA와 동일합니다.

?: Transition Function ?: Q X (? U ? ) -->2 ^ 질문.>

전환 함수에서 볼 수 있듯이 null(또는 ?)을 포함한 모든 입력에 대해 NFA는 모든 상태 수로 이동할 수 있습니다. 예를 들어, 아래는 위 문제에 대한 NFA입니다.

그림 2. NFA의 상태 전이 다이어그램 = {a, b}

위의 Automaton에 대한 상태 전이 테이블,

한 가지 중요한 점은, NFA에서 입력 문자열에 대한 경로가 최종 상태로 이어지는 경우 입력 문자열은 ~이다 수락됨 . 예를 들어 위 NFA에는 입력 문자열 00에 대한 경로가 여러 개 있습니다. 경로 중 하나가 최종 상태로 연결되므로 위 NFA에서는 00을 수락합니다.

몇 가지 중요한 사항:

정당화:

In case of DFA ? : Q X ? -->Q NFA의 경우? : 질문 X ? --> 2분기>

이제 관찰하면 Q X ? –> Q는 Q X의 일부인가요? –> 2^큐.

RHS 측에서 Q는 2의 부분 집합입니다.^큐이는 Q가 2에 포함되어 있음을 나타냅니다.^큐또는 Q는 2의 일부입니다.^큐그러나 그 반대는 사실이 아닙니다. 수학적으로 우리는 다음과 같이 결론을 내릴 수 있습니다. 모든 DFA는 NFA이지만 그 반대는 아닙니다. . 하지만 NFA를 DFA로 변환하는 방법이 있으므로 모든 NFA에 대해 동등한 DFA가 존재합니다. .

1. NFA와 DFA는 모두 동일한 권한을 가지며 각 NFA는 DFA로 변환될 수 있습니다.
2. DFA와 NFA 모두에 최종 상태가 여러 개 있을 수 있습니다.
3. NFA는 이론적인 개념에 가깝습니다.
4. DFA는 컴파일러의 어휘 분석에 사용됩니다.
5. NFA의 상태 수가 N이면 해당 DFA는 최대 2개를 가질 수 있습니다.^N상태의 수.

정규식 및 유한 오토마타에 대한 퀴즈를 참조하세요.