오늘날의 기술 시대에 하드웨어와 소프트웨어 분야 모두 엄청난 발전을 이루었습니다. 주요 개발 영역 중 하나는 하드웨어 설계 방법에서 보였습니다. 이랑 성장하는 기술 , 하드웨어 – 소프트웨어 공동 설계의 개념을 구현할 수있었습니다. 다양한 방법이 개발되며, 소프트웨어 사용 하드웨어 시스템을 완전히 설계하고 시뮬레이션 할 수 있습니다. 그러한 방법 중 하나가 Automata Theory입니다. Automata 이론은 컴퓨터 과학 그것은 미리 결정된 단계의 순서를 자동으로 따르는 컴퓨팅 장치의 추상 모델을 디자인하는 것을 다룹니다. 이 기사에서는 automata 튜토리얼에 대한 간략한 정보를 설명합니다.

Automata 이론은 무엇입니까?

Automata라는 단어는 그리스어에서 유래되었으며 '자기 행동'을 의미합니다. Automaton은 기계의 수학적 모델입니다. Automaton은 상태와 전환으로 구성됩니다. 입력이 자동으로 주어지면 전환 기능에 따라 다음 상태로 전환됩니다. 전환 기능에 대한 입력은 현재 상태 및 최근 기호입니다. Automaton에 유한 한 수의 상태가있는 경우 Finite Automata 또는 유한 상태 머신 . 유한 오토마타는 5- 튜플 (Q, ∑, δ, qo, F)로 표시됩니다.

어디,

Q = 유한 한 상태 집합.

∑ = 오토마타의 알파벳이라고도하는 유한 기호 세트.

δ = 전이 함수.

qo = 입력의 초기 상태.

F = Q의 최종 상태 세트.

Automata 이론의 기본 용어

Automata 이론의 기본 용어 중 일부는 다음과 같습니다.

1 . 알파벳 : 오토마타 이론의 유한 기호 집합은 알파벳으로 알려져 있습니다. 문자 ∑로 표시되는 집합 {a, b, c, d, e,}는 알파벳 집합이라고하며, 집합 'a', 'b', 'c', 'd', 'e'의 문자는 기호.

두 . 끈 : automata에서 문자열은 알파벳 집합 ∑에서 가져온 유한 한 기호 시퀀스입니다. 예를 들어, 문자열 S =‘adeaddadc’는 알파벳 집합 ∑ = {a, b, c, d, e,}에서 유효합니다.

“연산 증폭기 741을 사용하는 빈 브리지 발진기 ”

삼 . 문자열 길이 : 문자열에있는 기호의 수를 문자열 길이라고합니다. 문자열 S =‘adaada’의 경우 문자열 길이는 | S | = 6. 문자열의 길이가 0이면 빈 문자열이라고합니다.

4 . Kleen Star : 기호 집합 Σ에 대한 단항 연산자로, 집합 Σ에 대해 가능한 모든 길이의 λ를 포함하여 가능한 모든 문자열의 무한 집합을 제공합니다. 로 대표됩니다. 예를 들어 Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……} 집합의 경우.

5 . Kleen Closure : λ를 제외한 알파벳 집합의 가능한 모든 문자열의 무한 집합입니다. 로 표시됩니다. 세트 Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.

6 . 언어 : 언어는 일부 알파벳 집합 Σ에 대한 Kleene 별 집합 ∑ *의 하위 집합입니다. 언어는 유한하거나 무한 할 수 있습니다. 예를 들어 언어가 Σ = {a, d} 집합에 대해 길이 2의 가능한 모든 문자열을 사용하는 경우 L = {aa, ad, da, dd}입니다.

형식적인 언어와 오토마타

오토마타 이론에서 형식 언어는 문자열의 집합으로, 각 문자열은 기호로 구성 유한 알파벳 세트 Σ에 속합니다. 아래 무한 세트의 문자열을 포함 할 수있는 고양이 언어를 고려해 보겠습니다.
갈매기!
으으!
mewww !! ……

고양이 언어의 알파벳 세트는 Σ = {m, e, w,!}입니다. Finite State Automata Model-m에이 세트를 사용합니다. 그런 다음 모델 m이 특징으로하는 공식 언어는

L (m)
L (m) = {‘mew!’,‘meww!’,‘mewww’, ……}

Automaton은 무한한 집합을 닫힌 형태로 표현할 수 있기 때문에 언어 정의에 유용합니다. 형식적인 언어는 우리가 일상에서 말하는 자연어와는 다릅니다. 공식 언어는 일반 언어와 달리 기계의 다양한 상태를 나타낼 수 있습니다. 형식 언어는 구문 등과 같은 자연 언어의 일부를 모델링하는 데 사용됩니다. 형식 언어는 유한 상태 자동 장치에 의해 정의됩니다. Finite state automata-Acceptors에는 두 가지 주요 관점이 있습니다. 이는 문자열이 언어에 있는지 여부를 알 수 있고 두 번째 관점은 해당 언어의 문자열 만 생성하는 생성기입니다.

“디지털 전압계 전류계 회로도 ”

결정 론적 유한 오토마타

Deterministic type of automata에서 입력이 주어지면 언제 어떤 상태로 전환 될 것인지 결정할 수 있습니다. 이것은 유한 오토마타이기 때문에 결정 론적 유한 오토마타라고합니다.

그래픽 표현

State Diagram은 Deterministic Finite Automata의 그래픽 표현에 사용되는 digraphs입니다. 예를 들어 이해합시다. 결정 론적 유한 오토마타를…
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} 전환 기능은

그래픽 표현 테이블 형식

상태 다이어그램

결정 론적 유한 상태 오토마타의 상태 다이어그램

상태 다이어그램에서

상태는 정점으로 표시됩니다.
전환은 입력 알파벳으로 레이블이 지정된 호로 표시됩니다.
빈 단일 들어오는 호는 초기 상태를 나타냅니다.
이중 원이있는 상태가 최종 상태입니다.

비결정론 적 유한 오토마타

주어진 입력에 대한 출력 상태를 결정할 수없는 오토마타를 비 결정적 오토마타라고합니다. 유한 수의 상태를 가지고 있기 때문에 Non-Deterministic Finite Automata라고도합니다. 비 결정적 유한 오토마타는 5 – 튜플 세트로 표시됩니다. 여기서 (Q, ∑, δ, qo, F)

Q = 유한 한 상태 집합.
∑ = 알파벳 세트.
δ = 전환 기능

어디 : qo = 초기 상태.