L subscript 4 = {0,1} * - {0,01} *가되도록 DFA를 만들고 처음 5 개의 문자열을 사전 식 순서로 나열하십시오.DFA 찾기
L 첨자 4가 의미하는 바를 추론하는 데 문제가 있습니다. 길이 4의 문자열 언어입니까? 또한 두 언어를 빼면 빈 문자열에서 "1"을 뺀 문자열을 선택할 수 있습니다. 즉, 길이 0의 {0,01} *에서 길이 1을 뺀 첫 번째 {0,1} *을 선택할 수 있습니다. ?
언어 {0,01} *은 각 1 앞에 1이 있어야하는 문자열 집합입니다. 예를 들어 00010001은이 언어이지만 10000 또는 0001111은 그렇지 않습니다. 반면에 {0,1} *은 알파벳 {0,1}을 가진 모든 문자열입니다. 이제이 결과를 빼서 적어도 하나의 1이 있고 모든 1이 0보다 먼저 나온 언어를 말합니다. 예를 들어 1111000은 L_4에 있지만 000000 또는 011111은 아닙니다.
표기 {0, 1} * - {0, 01} *은 "{0, 1} *에없는 모든 문자열의 언어"를 의미합니다. " 그들은 쓸 때
L = {0, 1} * - {0, 01} *
나는 그들이 동일한의 L 라는 새로운 언어를 정의하고 생각 위의 식.
이 문제를 해결하려면 L 이 언어 {0, 01} *을 보완하는 것이 유용하다는 것을 알 수 있습니다. 이 문제를 해결하는 한 가지 방법은 {0, 01} *에 대한 DFA를 작성한 다음 수락 및 거부 상태를 모두 뒤집는 것입니다. 그러면 LFA 용 DFA가 제공됩니다 .
나머지 문제는 독자에게 연습으로 남깁니다. :-)
일반적으로 "L subscript 4"라는 이름의 언어를 의미합니다. – Bergi
문자열을 빼낼 수 없습니다. 'L_4 = L ({0,1} *) - L ({0,01} *)'이란 한 언어를 다른 언어에서 빼내야한다는 뜻일까요? – Bergi
당신이 맞습니다. Bergi, 저는 언어 {0,1} *을 의미합니다. 그러나 문자열을 통해 나는 언어가 만들어내는 긴장감을 의미합니다. – azureskys