이 컨텍스트는 무료입니까?

Question

시작 변수 S가있는 다음 문맥 자유 문법에 의해 정의 된 언어가 {0,1}이면 정규 언어입니까? S → TS, S → 1T, S → 1S T → TT, T → 0T1, T → 1T0 T → ε

이 언어는 정규입니까?

이 언어는 기본적으로 터미널과 변수의 조합이므로 정규 언어 일 수 없습니다. 정규 언어는 오른쪽 또는 왼쪽 선형이어야합니다. 내가 맞습니까, 아니면 내 생각이 틀 렸습니다. 컨텍스트없는 문법이 규칙적인지 판단하기 위해 누군가가 추천하는 특정 프로세스가 있습니까?

Answer 1

문법과 관련된 언어가 규칙적이 아닙니다. 게시물의 나머지 부분은이 진술의 증거와 관련이 있습니다.

먼저 L(T) = {w over {0,1} | w contains equal number of 0s and 1s}에 주목하십시오.

쉽게 증명할 수 있습니다.

증명 아이디어.(==>)w을 L(T)으로 가정합니다. 그런 다음 분명히 0과 1의 수가 같습니다.

(<==)w에는 0과 1이 동일하게 포함되어 있다고 가정합니다. w은 T에서 파생 될 수 있음을 유도로 보여줍니다. |w|<=2이면 T에서 분명하게 파생됩니다. 귀납적 가정에 대해, 길이가 모두 0,2 1, 1이 길이 인 k (길이가 균등) 인 모든 문자열은 T에서 파생 될 수 있다고 가정합니다. w의 길이는 k+2입니다. w의 첫 번째 문자와 마지막 문자가 일치하는 경우 (모두 0 또는 둘 모두 1), 제품 번호 T -> TT을 적용합니다. 첫 번째와 마지막 부분은 모두 귀납적 가정에 의해 T에서 파생 가능합니다. 여기서 우리는 w[0]=w[|w|-1] 일 경우 및 w[i+1..|w|-1]이 모두 L(T)에 있고 유도적 가설로 T에서 파생 될 수있는 색인 i이 존재한다는 명백한 속성을 사용하고 있습니다. 또는 w의 첫 번째 문자와 마지막 문자가 일치하지 않으면 T -> 0T1 또는 T -> 1T0을 사용하십시오. 결과 문자열은 길이가 k이고 귀납적 가정에 의해 T에서 유추 할 수 있습니다. QED.

이제는 문법 언어가 S에 의해 생성 될 수있는 문자열 집합입니다. S은 (T+1)*1T 양식의 문자열 (터미널 및 변수)을 생성합니다. 즉, 문법으로 유도 할 수있는 임의의 문자열 열 w의 경우 S =>* α =>* w 인 경우 여야합니다. 여기서 α은 (T+1)*1T입니다.

이제는 S에 의해 생성 될 수있는 모든 가능한 터미널 집합이 정규식 (L(T)* + 1)*1L(T)*을 특징으로한다는 것을 분명히해야합니다. (넌 (T+1)*1T로부터 생성 될 수있는 단말들의 스트링의 세트를 검사하여 도달 할 수있다.)

당신은 L(S)위한 표현을 단순화 할 수 (L(T)+1)*1L(T)=(L(T)+1)*를 1L(T)의 언어 (L(T)+1)^2 언어의 부분 집합이기 때문이다. 따라서 L(S) = (L(T)+1)*은 적어도 0과 1을 포함하는 이진 문자열로 구성된 언어입니다.

이 언어 은이 아닙니다. pumping lemma을 사용하여이를 증명할 수 있습니다.

증명. 모순을 위해서 L(S)은 정규적이라고 가정합니다. 그런 다음, 펌핑 보조 정리에 의해, 길이 적어도 n의 L(S)에서 모든 w가로 분류 될 수 있음을 n>0 같은있다 w=xyz 등 그 모든 k >= 0에 대한

1. |xy| <= n,
2. y 비어,
3. , xy^ky in L(S).

하자가 L(S)에서 길이 m=2n의 문자열 w=0^n1^n. 보조 정리는 에 대해 모두에서 L(S)으로부터 충분히 긴 문자열을 말합니다. 그래서 우리는 원하는 문자열을 선택하고 속성을 유지할 수 있습니다.) w=xyz을 보조 정리에 의해 존재하는 분할로 보자. 분명히, m=2n 및 |xy|<=n 이후로, 은 0s (및 y이 비어 있지 않으므로 적어도 하나는 0)로 구성됩니다.

분명히 xy^2z은 1보다 많은 0을 가지고 있으므로 L(S)에 없습니다. 이것은 펌핑 보조 정리와 모순됩니다. 따라서 L(S)은 정기적이지 않습니다. QED.