교과 과정: 문자열에서 하위 문자열을 검색하는 알고리즘. 실험 결과 및 분석. 직접 검색 알고리즘
이러한 작업의 가장 일반적인 적용은 문서 검색입니다. 일련의 참고문헌 목록으로 구성된 일련의 문서가 제공되며, 각 참고문헌에는 해당 참고문헌의 주제를 나타내는 "설명자"가 동반됩니다. 설명자 중에서 일부 키워드를 찾아야 합니다. 예를 들어 "프로그래밍" 및 "Java"에 대한 쿼리가 있을 수 있습니다. 이러한 쿼리는 다음과 같이 해석될 수 있습니다. "프로그래밍" 및 "Java" 설명자가 있는 기사가 있습니까?
문자열 검색은 공식적으로 다음과 같이 정의됩니다. N 요소의 배열 T와 M 요소의 배열 W가 주어지고 0이 됩니다.
직접 검색 알고리즘
알고리즘 아이디어:
1. 나는=1,
2. 배열 T의 첫 번째 문자를 배열 W의 첫 번째 문자와 비교합니다.
3. 일치 → 두 번째 문자 비교 등,
4. 불일치 → I:=I+1 그리고 포인트 2로 이동,
알고리즘 종료 조건:
1. M개의 연속적인 비교가 성공적입니다.
2. I+M>N 즉, 해당 단어를 찾을 수 없습니다.
알고리즘 복잡성:
최악의 경우. 배열 T→(AAA….AAAB), 길이 │T│=N, 샘플 W→(A….AB), 길이 │W│=M이라고 합니다. 분명히 문자열 끝에서 일치하는 항목을 찾으려면 약 N*M 비교, 즉 O(N*M)이 필요합니다.
알고리즘의 단점:
1. 높은 복잡성 - O(N*M), 최악의 경우 - Θ((N-M+1)*M);
2. 불일치 후 조회는 항상 패턴의 첫 번째 문자부터 시작하므로 이전에 검색한 T 문자가 포함될 수 있습니다(문자열을 보조 메모리에서 읽는 경우 이러한 반환은 오랜 시간이 걸립니다).
3. 주어진 교대 S를 확인할 때 얻은 텍스트 T에 대한 정보는 후속 교대를 확인할 때 어떤 방식으로도 사용되지 않습니다.
D. Knuth, D. Maurice 및 W. Pratt의 알고리즘(KMP 검색)
KMP 검색 알고리즘은 실제로 최악의 경우에도 N번 정도의 비교만 필요합니다.
예.
(비교된 문자에는 밑줄이 그어져 있습니다.) 
이미지 W의 초기 부분과 문자열 T의 해당 문자를 부분적으로 일치시킨 후, 실제로 문자열의 탐색된 부분을 알고 다음의 도움으로 일부 정보(이미지 W 자체를 기반으로)를 "계산"할 수 있습니다. 그런 다음 텍스트를 빠르게 이동할 수 있습니다.
KMP 검색의 아이디어는 텍스트의 두 문자와 이미지가 일치하지 않을 때마다 이동한 전체 거리만큼 이미지가 이동한다는 것입니다. 더 작은 이동으로는 완전한 일치로 이어질 수 없기 때문입니다.
KMP 검색의 특징:
1. 결과를 얻으려면 (N+M) 기호 비교 순서가 필요합니다.
2. KMP 검색 방식은 특정 횟수의 일치가 실패하기 전에만 진정한 승리를 제공합니다. 이 경우에만 이미지가 둘 이상 이동합니다. 불행하게도 우연은 불일치보다 훨씬 덜 일반적입니다. 따라서 대부분의 텍스트에서 KMP 검색을 통한 이득은 매우 미미합니다.
R. Bowyer 및 D. Moore의 알고리즘(BM 검색)
실제로 BM 검색 알고리즘은 패턴 W가 길고 알파벳 파워가 충분히 클 때 가장 효과적입니다.
BM 검색의 개념은 문자 비교가 샘플의 끝에서부터 시작되는 것이 아니라 처음부터 시작되지 않는다는 것, 즉 개별 문자의 비교가 오른쪽에서 왼쪽으로 발생한다는 것입니다. 그런 다음 일부 경험적 절차를 사용하여 오른쪽 이동 s의 양이 계산됩니다. 다시, 패턴의 끝부터 시작하여 문자를 비교합니다.
이 방법은 최악의 경우 처리를 향상시킬 뿐만 아니라 중간 상황에서도 이점을 제공합니다.
특별히 구성된 예를 제외하고 거의 항상 BM 검색에는 N 비교보다 훨씬 적은 양의 비교가 필요합니다. 가장 유리한 상황에서 샘플의 마지막 문자가 항상 텍스트의 일치하지 않는 문자에 속할 때 비교 횟수는 (N / M)과 같고 최악의 경우 - O((N-M+ 1)*M+ p), 여기서 p는 알파벳의 거듭제곱입니다.
Rabin-Karp 알고리즘(RK-검색)
알파벳 D=(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), 즉 알파벳의 각 문자는 d진 숫자이며, 여기서 d=│D│입니다.
예. 표본의 형식을 W = 3 1 4 1 5로 설정합니다.
길이 |W|=5 mod q의 창에서 숫자 값을 계산합니다. q는 소수입니다.
23590(모드 13)=8, 35902(모드 13)=9, 59023(모드 13)=9, …
k1=314157(mod 13) – 샘플 발생,
k2=673997(mod 13) – 유휴 작동.
등식 ki= kj (mod q)에서는 ki= kj를 따르지 않습니다(예: 31415=67399(mod 13). 그러나 이것이 31415=67399를 의미하지는 않습니다). ki= kj(mod q)이면 문자열 W와 T가 실제로 일치하는지 확인해야 합니다.
소수 q가 충분히 크면 유휴 트리거를 분석하는 데 드는 추가 비용이 작습니다.
최악의 경우 RK 알고리즘의 작동 시간은 Θ((N-M+1)*M)이지만 평균적으로 O(N+M) 시간에 매우 빠르게 작동합니다.
예: 다음과 같은 경우 RK 알고리즘은 몇 번의 유휴 작업 k를 수행합니까?
q= 11, 13, 17. W=(2 6)이라고 하자 
26 mod 11=4 → k =3 유휴 작업,
26 mod 13=0 → k =1 유휴 작동,
26 mod 17=9 → k =0 유휴 작업.
유휴 작업 횟수 k는 소수 q 값(샘플 처리 함수가 mod q인 경우)의 함수이고 일반적인 경우에는 샘플 W와 텍스트를 처리하는 함수 유형의 함수라는 것이 분명합니다. 티.
빠른 검색(분류 티에리 르크로크).
Bowyer-Moore 알고리즘에 사용된 잘못된 문자 이동은 작은 알파벳에는 그다지 효과적이지 않지만, 패턴의 길이에 비해 알파벳 크기가 큰 경우에는 자주 발생합니다.
텍스트 편집기에서 ASCII 테이블과 일반 검색을 수행하면 매우 유용해집니다. 알고리즘에서 이것만 사용하는 것은 매우 효과적일 수 있습니다.
x와 y를 결합하려고 시도한 후 이동 길이는 1 이상입니다. 따라서 기호 y [ i + m ]은 다음 시도에 확실히 포함됩니다. 이는 잘못된 위치를 이동하려는 현재 시도에 사용될 수 있음을 의미합니다. 상징. 마지막 x 기호를 고려하도록 잘못된 기호 함수를 수정해 보겠습니다.
bc[ a ] = min ( j | 0 j m 및 x[ m - 1 - j ] = a ), a가 x에 발생하면,
bc[ a ] = m 반대의 경우.
텍스트와 샘플 간의 비교는 순서에 관계없이 이루어질 수 있습니다.
티
목록 6
Urbo BM(분류 티에리 르크로크).
Turbo - BM은 Bowyer - Moore 알고리즘을 개선한 것이기도 합니다. 우리는 마지막 시도 동안 패턴 접미사와 일치하는 텍스트 세그먼트를 기억할 것입니다(그리고 좋은 접미사가 이동된 경우에만).
이는 우리에게 두 가지 이점을 제공합니다.
1. 이 구간을 뛰어넘는 능력
2. '터보 변속' 사용 가능성
텍스트와 일치하는 패턴 접미사가 이전에 기억한 것보다 짧다는 것을 발견하면 "터보 시프트"가 발생할 수 있습니다.
u는 기억된 세그먼트이고 v는 현재 시도 중에 일치하는 접미사입니다. 즉, uzv는 x의 접미사입니다. 그런 다음 av는 x의 접미사이고, 두 문자 a와 b는 텍스트의 거리 p에서 발생하며, 길이 |uzv|의 접미사 x입니다. 길이 p의 기간을 가집니다. 이는 텍스트에서 문자 a와 b의 모양을 모두 포함할 수 없음을 의미합니다. 가능한 가장 작은 이동의 길이는 |u|입니다. - |v| (우리는 이를 "터보 변속"이라고 부릅니다).
1.5. 유한 상태 기계를 사용하여 부분 문자열 찾기.
1.5.1. 기계의 구조.
정의에 따르면, 유한 자동장치는 5개의 M = (Q, q 0 , A, 
,
), 어디:
Q는 유한한 상태 집합입니다.
q 0 
Q - 초기 상태;
ㅏ 
Q는 수용 상태의 유한 집합입니다.
최종 입력 알파벳;
기능 Qx 
Q는 오토마톤의 전환 기능이라고 합니다.
처음에 상태 머신은 상태 q 0 에 있습니다. 그런 다음 입력 문자열에서 문자를 하나씩 읽습니다. 상태 q에 있고 기호 a를 읽으면 오토마톤은 상태 (q,a)로 이동합니다. 기계가 q A 상태에 있으면 입력 문자열의 일부를 읽을 수 있다고 말합니다. 만약 q 
그런 다음 해당 줄의 읽은 부분이 거부됩니다.
최종 상태 M과 관련된 함수는 다음과 같습니다. 
, 최종 상태 함수라고 하며 다음과 같이 정의됩니다. 
문자열 w를 읽은 후 자동 장치가 (초기 상태에서) 오는 상태가 있습니다. 자동인형은 A인 경우에만 문자열 w를 인정합니다.
각 샘플 P에 대해 텍스트에서 이 패턴을 검색하는 유한 자동 장치를 구축할 수 있습니다. 패턴 문자열 P에 해당하는 자동 장치를 구성하는 첫 번째 단계는 P에서 보조 접미사 함수를 구성하는 것입니다(KMP 알고리즘에서와 같이). 이제 패턴 P에 해당하는 상태 머신을 다음과 같이 정의합니다.
이 관계를 설명해보자. 문자열 T에 대해 작동할 때 관계가 다음과 같이 작동하도록 자동 장치를 구성해야 합니다.
(티) = 
(티)
불변이었습니다(그러면 동등성(T i) = m은 P가 i - m 시프트로 T에 들어가고 자동 장치가 허용되는 모든 시프트를 찾는다는 사실과 동일합니다). 그러나 이 경우 불변성의 참을 유지하기 위해 식 (1)을 사용하여 전이를 계산하는 것이 필요하며 이는 아래 정리에 따릅니다.
정리. q = (x)라고 가정합니다. 여기서 x는 문자열입니다. 그러면 임의의 기호 a에 대해 (xa) = (P q a)가 됩니다.
정리. 부분 문자열 P를 검색하기 위한 자동 장치의 최종 상태 함수라고 합니다. T가 임의의 텍스트인 경우 i=0,1,...,n에 대해 (T i) = (T i)입니다.
위에서부터 하위 문자열을 찾는 작업은 두 부분으로 구성됩니다.
패턴을 기반으로 자동 장치를 구축합니다(주어진 패턴에 대한 전환 기능 결정).
이 기계를 사용하여 주어진 텍스트에서 패턴의 발생을 검색합니다.
1.5.2. 유한 상태 기계를 구성하는 예
ababaca라는 문자열을 받아들이는 유한한 기계를 만들어 봅시다. 샘플 길이가 m = 7 기호이므로 기계는 m + 1 = 8 상태를 갖습니다.
전환 함수를 찾아보자. 정의 (1)에 따르면, (q, a) = (P q a), 여기서 는 접두사 함수이고, a는 알파벳의 임의 문자이고, q는 상태 번호입니다. 따라서 샘플 P의 각 접두사 P q = P, q = 0 .. m 및 입력 알파벳의 모든 기호 a에 대해 문자열 P의 접미사가 될 최대 접두사 P의 길이를 찾는 것이 필요합니다. q 가. 이 접두사의 길이는 전이 함수(q,a)의 값이 됩니다. a = P(텍스트의 다음 문자가 샘플의 다음 문자와 일치하는 경우)이면 P q a = P q +1이고 (q, a) = q+1입니다.
이 경우는 검색 성공 단계에 해당합니다. 그렇지 않으면 q. 예를 들어 접두사 P = ababa와 문자 b의 경우 접두사 P이기도 한 문자열 Pb = ababab의 최대 접미사는 abab입니다. 길이가 4이므로 전이 함수의 값 (5, b) = 4입니다.
이런 방식으로 구성된 전이 함수를 테이블 형식으로 작성해 보겠습니다(표 1).
행은 입력 기호에 해당하고 열은 기계 상태에 해당합니다. 성공적인 검색 단계(입력 문자가 다음 샘플 문자와 일치함)에 해당하는 셀은 회색으로 강조 표시됩니다.
표를 이용하여 아바바카 패턴을 인식하는 자동장치(그림 1)에 대한 전이 그래프를 구성해 보겠습니다. 상태 q에 있고 다음 기호 a를 읽은 후 기계는 상태 (q,a)로 이동합니다. 해당 뼈대에는 샘플 기호가 표시되어 있습니다(이러한 전환은 굵은 화살표로 강조 표시됨).
여기서 0은 초기 상태이고, 7은 유일한 허용 상태(검은색)입니다. 문자 a로 표시된 화살표가 정점 i에서 정점 j로 이어지는 경우 이는 (i,a) = j를 의미합니다. (i,a) = 0인 전이는 단순화하기 위해 전이 그래프에 표시되지 않습니다. 왼쪽에서 오른쪽으로 가는 굵은 화살표는 하위 문자열 P 검색의 성공적인 단계에 해당합니다. 다음 입력 문자는 샘플의 다음 문자와 일치합니다. 오른쪽에서 왼쪽으로 가는 화살표는 실패에 해당합니다. 다음 입력 기호는 패턴의 다음 기호와 다릅니다.
아래는 T=아바바바카바라는 텍스트에 기계를 적용한 결과입니다. 각 기호 T[g] 아래에는 이 기호를 읽은 후 기계의 상태(즉, 값(T i))가 기록됩니다(표 2).
패턴이 한 번 발견되었습니다(위치 3에서 시작). 발견된 샘플은 텍스트에서 회색으로 표시됩니다. 머신의 허용 상태(상태 번호 7)는 검은색으로 표시됩니다.
2부. 알고리즘의 실험적 분석.
2.1. 실험의 본질.
우리는 여러 알고리즘을 조사하고 시간 및 용량 복잡성을 평가했습니다. 그러나 이미 언급했듯이 이러한 평가 기준을 통해 어떤 알고리즘이 더 빨리 작동하는지 확실히 말할 수는 없습니다. 따라서 추가 평가를 위해 실험 분석을 수행합니다. 알고리즘이 특정 작업을 완료하는 데 걸리는 시간을 측정해 보겠습니다.
다음 형식의 항목 10,000개를 포함하는 여러 텍스트 파일이 있습니다.
선
하위 문자열(주어진 문자열에서 사용 가능)
입국 장소
하위 문자열 길이
문자열과 하위 문자열의 최대 길이가 다릅니다.
알파벳은 66개의 러시아어 대문자와 소문자로 구성됩니다.
10, 100, 250자를 넘지 않는 줄로 설정하세요.
각 알고리즘의 문자열에서 부분 문자열을 검색하여 프로그램의 실행 시간을 측정해 보겠습니다. 이를 위해 우리는 다음 사항을 고려할 것입니다:
라인은 배열 형태로 RAM에 미리 로드되며 배열을 읽는 시간은 고려되지 않습니다. 전처리(전이 테이블 생성)가 총 시간에 포함됩니다.
각 알고리즘은 5번씩 실행되며, 가장 짧은 시간이 선택됩니다.
실험대.
프로세서 Intel Pentium IV 2.66GHz
1024MB RAM
Borland Delphi Enterprise 컴파일러, 버전 6.0(빌드 6.163)
테스트 중인 프로그램의 코드 조각이 Listing 7에 나와 있습니다.
이러한 시간 측정은 프로세서의 특성과 부하에 직접적으로 의존하기 때문에 매우 모호한 결과를 제공한다는 것이 분명합니다. 따라서 실험 중에는 프로그램 작동에 영향을 미치지 않는 모든 타사 및 백그라운드 응용 프로그램이 비활성화되었습니다. 동일한 작업을 실행할 때 시간이 다를 수 있으므로 여러 번 실행하여 최상의 결과가 선택됩니다.
2.2. 실험 결과 및 분석.
실험은 알고리즘 클래스를 대표하는 네 가지 알고리즘에 대해 수행되었습니다. 모든 알고리즘을 동일한 조건에 두었기 때문에 비교 분석이 가능합니다. 이 분석은 이러한 검색 매개변수에만 적용 가능하며 다른 조건에서는 다를 수 있습니다.
실험 결과이를 표(표 3)에 올려보자.
예상대로 Boyer-Moore 알고리즘은 다른 알고리즘보다 실험 작업을 더 빠르게 처리했습니다. 그러나 그 효과는 라인 길이와 그에 따른 샘플 길이가 증가함에 따라 증가한다는 점에 유의해야 합니다. 그래서 문자열 길이가 10자 이하일 경우 순차검색보다 성능이 나빴습니다. KMP 알고리즘은 짧은 단어와 긴 단어 모두에 대해 유사한 결과를 보여줍니다. 문자열과 패턴 길이를 알 수 없는 경우 범용으로 사용할 수 있습니다.
Rabin 알고리즘은 순차 알고리즘과의 유사성에도 불구하고 더 빠르게 작동하며 구현에 대한 단순성과 낮은 인건비로 인해 비특수 프로그램에 사용하기에 매력적입니다.
최악의 결과는 순차 검색 알고리즘에 의해 나타났다. 예상대로 문자열 길이가 약간만 늘어나도 다른 알고리즘에 비해 몇 배 느리게 작동합니다.
이 실험에는 유한 상태 기계를 사용한 검색 알고리즘이 포함되어 있지 않습니다. 우리는 러시아 알파벳 66자로 구성된 알파벳을 사용하는데, 제작된 기계가 너무 부피가 커질 것입니다. 이 알고리즘의 효율성은 알파벳 문자 수가 적을수록 증가합니다.
결론.
문자열에서 부분 문자열을 검색하기 위한 다양한 알고리즘을 살펴보고 분석했습니다. 결과는 표(표 4)로 제시될 수 있다.
|
연산 |
이전 시간 처리 |
평균 검색 시간 |
최악의 검색 시간 |
메모리 비용 |
라인 길이가 250 이하인 경우 실행 시간(ms) |
노트 |
|
순차 검색 알고리즘을 기반으로 한 알고리즘 |
||||||
|
직접 검색 알고리즘 |
O((m-n+1)*n+1)/2 |
프로그램에 대한 인건비가 낮고 효율성이 낮습니다. |
||||
|
라빈의 알고리즘 |
||||||
|
크누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘 |
||||||
|
샘플 길이를 알 수 없는 경우 범용 알고리즘 |
||||||
|
보이어-무어 알고리즘 |
||||||
|
이 그룹의 알고리즘은 일반적인 상황에서 가장 효과적입니다. 패턴이나 알파벳이 증가할수록 성능이 향상됩니다. |
||||||
얻은 결과에 따르면 Boyer-Moore 알고리즘이 모든 측면에서 선두를 달리고 있음이 분명하며 가장 효과적인 알고리즘을 찾은 것 같습니다. 그러나 실험에서 알 수 있듯이 Knuth-Maurice-Pratt 알고리즘은 작은 샘플 길이에서 BM 알고리즘보다 우수합니다. 따라서 어떤 알고리즘이 가장 최적이라고 결론을 내릴 수 없습니다. 각 알고리즘을 사용하면 해당 문제 클래스에 대해서만 효과적으로 조치를 취할 수 있으며 이는 좁게 목표를 정한 다양한 개선 사항에서도 입증됩니다. 문자열에서 하위 문자열을 검색하는 알고리즘은 프로그램이 수행해야 하는 작업을 정확하게 정의한 후에만 선택해야 합니다.
이러한 결론을 내림으로써 우리는 이 작업의 목적을 달성했습니다. 다양한 종류의 문제에 대해 우리 자신의 효과적인 알고리즘이 식별되었습니다.
서지 목록.
1). 커츠, 세인트. 선언적 패턴 일치 시스템의 기본 알고리즘 [텍스트]. – 빌레펠트:. Universität Bielefeld, 1995. - 238 페이지.
2). Lecro, T. 정확한 문자열 일치 알고리즘 [전자 자원]. 액세스 모드 http://algolist.manual.ru/
삼). Akhmetov I. 유한 상태 기계를 사용하여 부분 문자열 검색 [텍스트]: 교과 과정 - SP State University of Information Technologies, Mechanics and Optics.
4). 아호, Alfred 데이터 구조 및 알고리즘 [텍스트]. – M.: Williams Publishing House, 2000. - 384p.
5). Belousov A. 이산 수학 [텍스트]. – M.: MSTU im의 출판사. N.E. 바우만, 2001. – 744p.
6). 브라이언, K. 프로그래밍 연습 [텍스트] - 상트페테르부르크:. Nevsky 방언, 2001. - 381 p.
7). Wirth, N. 알고리즘 및 데이터 구조 [텍스트] – M:. 미르, 1989. – 360p.
8). 길, 아트. 유한 오토마타 이론 소개 [텍스트]. – M., 1966. - 272p.
9). Glushakov S. 프로그래밍 웹 페이지 [텍스트]. – M .: AST Publishing House LLC, 2003. – 387 p.
10). Knuth, D. 컴퓨터 프로그래밍 기술 [텍스트]: 3권. – M:. 미르, 1978. – 356p.
열하나). Sailor D. 추상 및 컴퓨터 대수학 요소 : 교과서. 학생들을 위한 지원 교육 대학 [텍스트]. – M .: 출판 센터 “아카데미”, 2004. – 240 p.
12). Uspensky V. 알고리즘 이론: 주요 발견 및 응용 [텍스트]. – M .: Nauka, 1987. – 288 p.
13). Shen, A. 프로그래밍: 정리와 문제 [텍스트]. – M.: 모스크바 평생 수학 교육 센터, 1995.
14). Kormen, T. 알고리즘: 구성 및 분석 [텍스트] / T. Kormen, Ch. Leiserson, R. Rivest - M.: MTsNMO, 2002. M.: MTsNMO, 2002.
추상 기계 밀리
추상 합성 1. 트리거 수를 선택합니다. 머신에는 5개의 상태가 있으므로 q=]log25[=3개의 트리거가 필요합니다. 2. 입력의 내부 상태 코딩...
문자열에서 하위 문자열을 검색하는 알고리즘
ababaca라는 문자열을 받아들이는 유한한 기계를 만들어 봅시다. 샘플 길이가 m = 7 기호이므로 기계는 m + 1 = 8 상태를 갖습니다. 전환 함수를 찾아보자. 정의 (1)에 따르면, (q, a) = (Рqа), 접두사 함수는...
고급 언어 어휘 및 파서
위에서 명시된 문법에 대한 어휘 분석기의 제어 테이블은 표 2에 나와 있습니다. 이 제어 테이블을 구현하는 프로그램 목록은 부록 A에 나와 있습니다.
유한 상태 기계의 Lisp 구현
유한 상태 기계(Finite State Machine)는 현재 상태와 입력 데이터에 따라 객체의 상태를 변경하는 방법을 설명할 수 있는 알고리즘 이론의 수학적 추상화입니다.
인터넷에서 정보 검색하기
유한 상태 머신은 출력 스트림이 없는 추상 머신으로, 가능한 상태의 수가 유한합니다. 기계 작동의 결과는 최종 상태에 따라 결정됩니다. 유한 상태 기계를 지정하는 데는 다양한 옵션이 있습니다. 예를 들어...
실생활에 자동 프로그래밍 적용
표를 사용하여 오토마타를 설명하는 것이 편리하고 명확성을 위해 그래프를 사용합니다. 테이블을 기술할 때 두 개의 테이블이 지정됩니다.
컴퓨터 제어 장치를 위한 유한 상태 기계의 합성
유한 상태 기계 KA(그림 1)의 일반화된 블록 다이어그램에는 저장 장치(트리거 T1-Tn의 메모리)와 신호 q1, q2,...를 생성하기 위한 두 개의 조합 장치 KU가 포함되어 있습니다.
비결정론적 유한 자동장치는 5중 A=(Q,V,M,S,Z)입니다. 여기서 Q는 내부 상태의 집합(알파벳)입니다. V - 알파벳 입력; M - 전환 기능...
유한 인식 기계의 합성
결정론적 유한 자동장치는 5중주 A=(Q,V,M,S,Z)입니다. 여기서 Q는 상태의 알파벳입니다. V - 알파벳 입력; M - 전이 함수(Q*VP(Q)); S - 초기 상태; Z - 최종 상태 세트; SZ. 이 기계에서는...
유한 인식 기계의 합성
유한 상태 기계의 작동을 시뮬레이션하는 프로그램은 허용되는 체인과 허용되지 않는 체인 간의 구별을 보장합니다. 컴퓨터 키보드에서 문자열을 입력하면 문자열을 구별하는 프로그램이 자동으로...
자동 문법을 사용하여 비결정적 자동 장치를 구성하는 절차: 1. 자동 장치의 입력 집합은 문법의 터미널 집합이 됩니다. 2. 자동장치의 상태 집합은 문법의 비종단 집합이 됩니다.
인식기의 합성
비결정적 자동장치에서 결정적 자동장치로 전환하는 절차: 명칭: AD - 결정적 자동장치 AN - 비결정적 자동장치 1...
유한 상태 기계의 구조적 합성을 위한 표 형식 방법
유한 오토마타 S를 지정하려면 S(A, X, Y, d, d)의 5개 개체 집합을 지정해야 합니다. 여기서 A = (a0,a1,a2,.,an)은 내부 개체 집합입니다. 오토마톤의 상태, X = (x1, x2,…, xm) - 입력 신호 세트(입력 알파벳), Xi는 입력 알파벳의 문자, Y = (y1, y2...
유한 상태 기계의 동등성과 최소화
상태 수가 다르더라도 상태 머신은 동일한 방식으로 작동할 수 있습니다. 중요한 작업은 주어진 오토마톤 매핑을 구현하는 최소 유한 상태 머신을 찾는 것입니다.