0
A
답변
1
번호 예 : 알파벳은
입니다. 숫자는
입니다. DFA는 모든 자연수를 허용합니다. 하위 집합 : DFA는 모든 소수를 허용합니다.
편집 : 알파벳은 숫자입니다. 죄송합니다. 잘못된 용어가 있습니다.
자연 번호 는 일반 언어로 표현 될 수있다 (그리고 따라서 DFA는 그들을 위해 구성 할 수있다) :
0|([1-9][0-9]*)
1
모든 유한 오토마타 - 결정적뿐만 아니라 결정적를 - 할 수있다 정규 언어로 표현되고 그 반대의 경우도 마찬가지입니다. 언어의 하위 집합이 정규 인 경우 예을 DFA로 나타낼 수 있습니다.
+0
나는 이것이이 질문에 답하는 것을 믿지 않는다. 문제는 일반 언어의 모든 하위 집합도 규칙적이어야하는지 여부이며, 이는 거짓이며 여기에서 다루지 않습니다. – templatetypedef
+0
요점은 다음과 같습니다. 일반 언어의 하위 집합이 정규 언어로 보장되지 않습니다. –
사실, 언급 한 언어 중 어느 것도 정규입니다. 둘 다 무한합니다. 소수를 사용할 수있는 DFA가 없기 때문에 소수의 언어는 정규 언어가 아닙니다. – Marcin
@Marcin 정규 표현식이 실제로 [[0-9] *'와 같이 무한한 문자열을 표현할 수 있다는 것을 잊고 있습니다. – bdares
아니요. 허용 할 수있는 단어의 길이에 상한이 없음을 나타냅니다. 그러나 받아 들여지기 위해서는 어떤 수락 상태에 도달해야하며, 그 후에는 더 이상의 요소가 없다. 더구나, 이것은 무한한 알파벳을 갖는 것과 같은 것이 아닙니다. – Marcin