불가능한 유한 상태 오토 마트?

필자는이 결정적이지 않은 FSA가 모든 시도에서 가능하지 않다고 믿습니다. FSA (Non Deterministic) : 언어는 홀수의 자릿수 (223, 32232)를 갖는 문자열 내에서 2와 3의 알파벳으로 구성되며 숫자의 합은 5로 나눌 수 있어야합니다. (최종 포함 예 : 22222, 33333, 2222322).불가능한 유한 상태 오토 마트?

누군가 그래픽으로 수용 상태로이 비 결정적 FSA를 구성 할 수 있습니까? 내 시도와 동료 중 한 사람이 모두 할 수 없다는 점에서 매우 인상 깊었습니다.

출처

2014-04-10 Glenn-Mac

처음으로 홀수 길이를 허용하는 주소를 작성하십시오. 그런 다음 숫자 합계가 5로 나눌 수있는 숫자를 허용하는 것을 작성하십시오. 그런 다음 제품을 가져 가십시오. –

@ RaymondChen - 하나의 FSA 다이어그램이 있어야합니다. –

두 개부터 시작하십시오. 그런 다음 표준 기술을 사용하여 이들을 하나에 병합하십시오. –

먼저 NFA가 아닌 FSA라고 생각합니다. 모든 정규 표현식을 NFA로 변환 할 수 있습니다. 그러나 RE에서 모든 언어를 지정할 수있는 것은 아닙니다. 너 같은 것이 그럴 수있다. 다음은 두 가지 간단한 예입니다. RE는 괄호가 균형을 잡았는지 여부를 확인하거나 문자열의 A와 B가 같은지 여부를 확인하는 데 사용할 수 없습니다. 그래서 당신이 당신의 문제에 대한 RE를 찾을 수 있다면, 당신은 끝났습니다.

출처

2014-04-10 06:46:19 Marichyasana

나는 ** (22222 | 33333) * (23 | 32) + **까지 얻지 만 RE의 처음 두 가지 옵션 중 하나의 끝 부분에서 3을 혼합 할 수는 없다. 무한한 순열의 @Marichyasana –

불가능한 유한 상태 오토 마트?

답변

관련 문제