0
A
답변
1
먼저 CFG가 생성하는 언어를 살펴 보겠습니다. 사실 꽤 복잡한 언어입니다. S를 하나만 확장하면 abc(b(b*))이됩니다. 두 사람은 ab[abc(b(b*))]c(b(b*)), 세 사람은 ab[ab[abc(b(b*))]c(b(b*))]c(b(b*)) 등이 될 것입니다. S 전환에서 추가 된 부분을 대괄호로 묶었습니다. 이 언어는 {(ab)^n (c(b(b^x_i)))^m} 인 것처럼 보입니다. 여기서 x_i은 0보다 크거나 같은 정수이며, 각 x_1, x_2, ... , x_i은 다를 수 있습니다. N 및 미터는 PDA로 변환 0
에게 모두 정수 이상인, 우리는 쉽게 부품을 시작할 수있다. 귀하의 알파벳은 {a, b, c}이고, "ab"섹션에 대한 상태와 "c (b (b^x_i)"부분에 대한 상태가 필요합니다. 두 번째는 q입니다. 스택 알파벳은 {bottom, A, C}입니다. 하단은 단순히 스택 맨 아래에 도달했음을 나타내는 기호입니다. 이제는 어려운 부분 인 델타 전환이 빈 스택에 의해 수용됩니다 :.
(p,e,bottom),(p,e) - this is for "m" = 0, accepting the empty string "e" or the case (ab)^n (this is an accepting state)
(p,a,bottom),(p, A bottom) - if we read an "a" and the stack is empty, push an A to the stack
(p,b,A),(p,e) - if we get a "b" and there was already an A on the stack, remove it
(p,c,bottom),(q,C bottom) - if we get a "c" and the stack was empty (i.e. we've finished the (ab)^n section), go to state q and push a C onto the stack
(q,b,C),(q,e) - if we get a "b" after a c, remove the C from the stack
(q,b,bottom),(q,bottom) - if we get a "b" in the b^x_i section, pop then immediately push bottom onto the stack
(q,c,bottom),(q,C bottom) - if we get a "c" after the b^x_i section, push a C onto the stack
(q,e,bottom),(q,e) - if we finish our string and our stack is empty (as it should be), then this is an accepting state
빈 문자열을 읽고 빈 스택을 생산 위의 전환을 받아들이는 상태입니다 허용되지 않습니다 모든 전환 (예는 "C"를 받고 이미 스택에 C있을 때) 포함되지 않음
희망이 도움이됩니다!