나는 형식 언어와 Automata 이론을 공부하고있다, 그리고 책 안에 대답이없는 문제에 대한 질문이있다. 질문입니다 :이 문법이란 무엇입니까? 문맥 또는 문맥에 민감한
이 문맥은 무료, 일반 또는 상황에 맞는가요?
L = {A Nw w R B N | w는 (a + b) * R 승는 w의 역방향이고, n> = 0}
I 그것을 수용하기위한 적어도 두개의 스택을 필요 원인이 언어는 문맥 감지 생각된다.
아무도 언급하지 않을 수 있습니까?
감사합니다.
언어 R B 승 N는 문맥 자유 언어가 N 승. 이 언어에 대한 문맥이없는 문법을 작성할 수 있습니다.
S --> aSb | R
R --> aRa | bRb |^
^가 영 기호를이다
PDA : 언어의 N와트 R B N
anwRbn참고 b에 대해 스택과 일치 밀어 모든 a에 기호에 대한 각각의 기호와 일치하면서 w
w 언어의 a n ww R b 이 언어에 대해 우리가 deterministic model of PDA although Non-deterministic PDA is possible을 그릴 수 없도록 w이 wR가 시작되기 전에 끝나는 접두사 an 다음 끝나는 PDA를 통해 N 우리는 알지 못한다. 중요한 것은 비 결정적 PDA의 클래스가 결정적인 PDA의 클래스와 같지 않음을 의미하는 scope deterministic context free languages are not equals to non-deterministic context free.을 의미합니다 (실제로 결정 성은 비 결정적 CFL의 하위 집합입니다)* 내 대답이 도움이되는지 또는 더 자세한 정보가 필요하다는 것을 알려주십시오 * –
NPDA 에서조차 조금 혼란 스럽습니다. W 팝업이 중지되고 스택 내용을 분석하여 b 접미어를 시작합니다. 예를 들어 aaa aab baa bbb가 있으면 aaa를 누르고 aab을 누르고 b - a - a - 이제 팝업을 멈추거나 b를 넣는 것을 알 수 없습니다. 감사합니다. –
aa babab baabb bb (a, a, b, b, a, a, b)를 입력하면 다음과 같이 팝업이 시작됩니다 : 스택의 최상위가 입력과 같으면 pop이 다음 입력으로 이동하여 반복합니다. 그렇지 않으면 스택의 최상위가 아닌 경우 스택이 비어있을 때까지 입력, 팝 스택 및 풋 b와 같음 ... 이렇게하면 하나의 스택에서이를 수용 할 수 있습니다. –
왜 두 개의 스택이 필요하다고 생각합니까? 단일 스택에 결합 할 수 없다고 확신합니까? – ibid
@ibid : 하나의 스택은 a를 내부에 넣음으로써 하나의 스택을 저장하고, 하나의 스택은 W를 저장하고, W 요소를 반전시켜 첫 번째 스택의 팝마다 마지막에 b를 붙여서 a의 수.알다시피, 당신은 W와 R을 같은 스택에 병합 할 수없고 W 나 R (W)가 끝날 때를 알 수 없습니다. 그래서 우리는 두 개의 스택이 필요합니다. 의견을 말할 수 있습니까? –
이미 내가 만든 포인트를 만드는 대답이 있습니다 :-) – ibid