automata-theory Archives - Page 6 of 10

문맥없는 언어를 인식하기 위해 결정적이지 않은 푸시 다운 오토마타 (DPA = NPDA) 만 작동하는 이유를 알고 싶습니다. 결정 론적 푸시 다운 오토마타 (DPDA)가 왜 그런 언어를 인식하지 못합니까?

답변

나는 당신이 찾고있는 “왜”의 맛을 잘 모르겠습니다. 비결 정성을 허용 할 때 전력이 증가하는 한 가지 이유는 다음 예에서 볼 수 있습니다.

하자 회문들의 집합 일부 알파벳 (적어도 두 개의 심볼) 이상, 의 역이다 . 이 언어의 NPDA는 기호를 스택에 계속 밀어 넣은 다음 입력의 중간에 도달하여 점진적으로 스택을 비 웁니다. 수용 조건은 순전히 존재한다는 점에 유의하십시오. 단어를 받아 들일 수있는 정확한 추측이 있으면 충분합니다. $L$

$w \bar{w}$

ww¯

$\bar{w}$

w¯

$w$

결정 론적 PDA는 현재 접두사에만 의존하는 방식으로 중간을 고려하는 위치를 선택해야합니다. 가 그러한 DPDA라고 가정하십시오 . 임의의 경우 ,하자 ; 하자 비어있는 단어, 그리고 . 이는 그래서, 회문 시퀀스 다음 각 접두사 받아들이는 상태에 있어야 스택 읽은 후, 공창, . 비둘기 구멍 원리에 의해 및 과 같은 이 있어야합니다. $A$

$k \in N$

k∈N

$u_{k} = a b^{2 k} a$

uk=ab2ka

$v_{0}$

$v_{k + 1} = v_{k} u_{k} v_{k}$

vk+1=vkukvk

$A$

$q_{k}$

$v_{k}$

$k, l$

k,l

$k \neq l$

k≠l

$q_{k} = q_{l}$

qk=ql

(유한 한 수의 상태가 있으므로 무한 수의 가 있으므로 일부는 ‘재사용’해야합니다 ). 그러나 구별 할 수 에서, 회문 인 하지 않습니다. $k$

$A$

$v_{k} u_{k} v_{k}$

vkukvk

$v_{l} u_{k} v_{k}$

vlukvk

답변

FA는 결정 론적이거나 비결정론 적으로 동일한 언어 (예 : Regular Lang)를 허용합니다.

그러나 PDA 의 경우 결정적 으로 동작하도록 제한하면 일부 CFL ( 접두사 속성이없는 CFL ( RL 제외))을 허용하지 않습니다 .

왜 그래?

접두사 속성이없는 CFL의 예를 고려하십시오 (lang의 접두사 속성 : 문자열이없는 경우 lang에있는 다른 문자열의 올바른 접두사가 없습니다).

L = wwr

예. 문자열 00 및 0000 . (00은 올바른 접두사 0000이므로 wwr에는 속성이 없습니다).

00 DPDA가 발생 하면 최종 상태가됩니다. 이제 DPDA이 acceptancy 연속성 사이에 선택의 여지가 없기 때문에 , 그것을 받아 들일 수 없습니다 0000을 수용 한 후 00 . PDA가 비결 정성을 요구하는 곳 입니다.

관찰 : FA의 경우 lang (RL) pref. 속성은 결정적으로 받아 들일 수 있습니다 (예 : 0으로 시작하는 문자열). 이것은 RL과 CFL의 접두사 속성의 효과가 다르다는 것을 보여줍니다 . PDA에 대한 결정론과 비결정론의 차이점은 새로운 언어 군을 만들어 낸다. DPDA에 의해 허용됩니다. 이 언어를 DCFL 이라고 합니다.

답변

Exit mobile version

How IT

언제든지 물어보세요.

태그 보관물: automata-theory

비결정론 (푸시 다운 오토마타)이 필요한 이유는 무엇입니까? 만 작동하는 이유를

답변

답변

답변