빈 스택으로 받아들이는 푸시다운 오토마타에 대한 입력의 총 길이는 숫자 상태와 스택 기호의 상한입니다.

Question

나는 고전적인 텍스트를 읽고 있었다 Jeffrey Ullman, John Hopcroft, Rajeev Motwani의 "오토마타 이론, 언어 및 계산 소개"(3판), 여기서 빈 스택을 허용하는 푸시다운 오토마타(PDA)에 대한 다음과 같은 몇 가지 진술을 발견했습니다.

1. $n$, 입력의 전체 길이는 확실히 상태 및 스택 기호 수의 상한입니다.

2.하나의 규칙은 스택에 거의 n개의 기호를 배치할 수 있습니다.

저자가 CFL(Context Free Languages)의 결정 속성에 대해 몇 가지 메모를 하려고 하는 동안 다음과 같은 진술이 이루어졌습니다.

이제 주장이 옳다는 것을 증명하기보다는 주장을 반박할 수 있는 몇 가지 요점이 있습니다.

1. 가정하다 $n$, 는 입력의 전체 길이이지만 PDA의 설계에 따라 입력 문자열을 받아들이는 데 PDA의 모든 상태가 포함되지 않을 수도 있으므로 이를 통해 다음과 같이 말할 수 없습니다. $n$ PDA가 갖는 상태 수의 상한입니다.

2. PDA가 빈 스택을 받아들이더라도 전환 기능이 다음보다 더 많은 것을 추가하는 일이 발생할 수 있습니다. $n$ 요소는 스택 상단에 있지만 마지막에는 요소를 소비합니다. $n$ 입력 기호는 특정 상태를 유지하고 엡실론 전환을 사용하여 동일한 상태를 유지하고 스택이 비워질 때까지 스택에서 요소를 팝할 수 있습니다.그러면 우리는 어떻게 그렇게 말할 수 있습니까? $n$ 스택의 요소 수에 대한 상한은 무엇입니까?우리는 모순에 도달했습니다 ...

제가 어디에서 실수를 하고 있는지 이해가 되지 않습니다. 왜냐하면 두 번째 판에서는 아무런 변경도 없이 같은 진술이 책의 세 번째 판에 기록되어 있기 때문에 그 진술이 정확할 가능성이 높기 때문입니다.

아래 텍스트의 해당 부분을 첨부했습니다.

Answer 1

해당 섹션에서는 구문 분석에 대해 이야기하지 않습니다.언급된 알고리즘은 서로 다른 유형의 CFG와 PDA 간의 변환을 위한 알고리즘입니다.질문은 평소와 같이 "알고리즘의 계산 복잡성은 무엇입니까?"이며 응답은 평소와 같이 입력 크기로 표현됩니다. 알고리즘에.

PDA를 CFG로 변환하는 알고리즘에 대한 입력은 PDA이고, 입력의 크기(알고리즘의 복잡성을 나타내는 척도)는 *PDA의 크기입니다.작가가 의도한게 바로 그거임 N 장차 ~ 가 되는.

PDA의 크기를 어떻게 측정합니까?단순한:일부 PDA 정의 언어에서 문자열로 PDA를 작성하고 설명에서 기호를 계산합니다.PDA에서 변환 알고리즘을 호출하려면 PDA를 나타내는 입력을 변환기에 제공해야 하기 때문에 이는 완전히 공정한 절차입니다.

이러한 정의를 고려하면 이러한 주장은 전혀 놀라운 것이 아닙니다.모든 주와 모든 알파벳 기호는 PDA 설명에 최소한 한 번 이상 나타나야 하므로 해당 설명의 크기는 상한입니다.마찬가지로, PDA에 대한 대부분의 설명은 단일 규칙에 대한 설명일 가능성이 있습니다. n 기호.