logo

DFA의 예

예시 1:

∑ = {0, 1}로 FA를 설계하면 1로 시작하고 0으로 끝나는 문자열을 허용합니다.

해결책:

FA는 입력 1이 있는 에지만 다음 상태로 이동하는 시작 상태 q0을 갖습니다.

결정론적 유한 오토마타의 예

상태 q1에서 1을 읽으면 상태 q1에 있게 되고, 상태 q1에서 0을 읽으면 최종 상태인 q2 상태에 도달하게 됩니다. 상태 q2에서 0이나 1을 읽으면 각각 q2 상태 또는 q1 상태로 이동합니다. 입력이 0으로 끝나면 최종 상태가 됩니다.

예 2:

∑ = {0, 1}인 FA를 설계하면 입력 101만 허용됩니다.

해결책:

결정론적 유한 오토마타의 예

주어진 솔루션에서는 입력 101만 허용되는 것을 볼 수 있습니다. 따라서 입력 101의 경우 다른 입력에 대해 표시되는 다른 경로가 없습니다.

Java 파일을 한 줄씩 읽습니다.

예시 3:

∑ = {0, 1}인 FA 설계는 0의 짝수와 1의 짝수를 허용합니다.

해결책:

이 FA는 입력 0과 입력 1에 대해 4가지 다른 단계를 고려합니다. 단계는 다음과 같습니다.

결정론적 유한 오토마타의 예

여기서 q0은 시작 상태이고 최종 상태이기도 합니다. 0과 1의 대칭이 유지된다는 점에 주의하세요. 다음과 같이 각 상태에 의미를 연관시킬 수 있습니다.

q0: 0이 짝수이고 1이 짝수인 상태.
q1: 0이 홀수, 1이 짝수인 상태.
q2: 홀수개의 0과 홀수개의 1의 상태.
q3: 0이 짝수이고 1이 홀수인 상태.

예시 4:

∑ = {0, 1}인 FA 설계는 세 개의 연속된 0이 있는 모든 문자열 집합을 허용합니다.

해결책:

이 특정 언어에 대해 생성될 문자열은 000, 0001, 1000, 10001, ...입니다. 여기서 0은 항상 3 덩어리로 나타납니다. 전환 그래프는 다음과 같습니다.

결정론적 유한 오토마타의 예

최종 상태에 도달하기 위해 삼중 0의 순서가 유지됩니다.

예시 5:

DFA 설계 L(M) = {w | w ε {0, 1}*} W는 연속된 1을 포함하지 않는 문자열입니다.

해결책:

세 개의 연속 1이 발생하면 DFA는 다음과 같습니다.

자바가 포함된 mvc
결정론적 유한 오토마타의 예

여기서는 두 개의 연속된 1 또는 단일 1이 허용됩니다.

결정론적 유한 오토마타의 예

q0, q1, q2 단계는 최종 상태입니다. DFA는 10, 110, 101 등과 같은 연속적인 1을 포함하지 않는 문자열을 생성합니다.

예시 6:

∑ = {0, 1}로 FA를 설계하면 짝수 0 뒤에 단일 1이 오는 문자열을 허용합니다.

해결책:

DFA는 전환 다이어그램으로 다음과 같이 표시될 수 있습니다.

결정론적 유한 오토마타의 예