DFA에서 PDA로 변환

Question

Deterministic Finite Automata를 Push Down Automata로 변환하는 알고리즘을 찾고 있습니다.

도움을 주시면 감사하겠습니다.

감사합니다.

Answer 1

wikipedia article는

푸시 다운 오토마타는 두 가지 방법으로 유한 상태 머신과 다를 말한다 :

1. 그들은 전환에 테이크를 결정하는 스택의 상단을 사용할 수 있습니다.
2. 전환을 수행 할 때 스택을 조작 할 수 있습니다.

푸시 오토마타는 입력 신호 현재 상태, 스택의 상단 기호로 테이블을 인덱싱하여 전이 를 선택한다. 즉, 세 개의 매개 변수를 모두 으로 지정하면 전환 경로가 으로 결정됩니다. 유한 상태 기계는 입력 신호를보고 현재 상태 : 에 대한 스택이 없습니다. 푸시 다운 오토 마톤은 스택을 선택 매개 변수로 추가합니다.

는 ...
푸시 다운 오토 마톤은 문맥 자유 문법 동등하다 : 모든 문맥 자유 문법를 들면, 푸쉬 다운 오토 마톤 존재 문법에 의해 생성 된 언어 생성 언어 동일하다고 은 쉽게 알 수있는 오토 마톤에 의해 증명합니다. 열심히 가 증명하지만 그 반대가 사실이다 : 모든 푸시 자동 장치의 자동 장치에 의해 생성 된 언어 문법에 의해 생성 언어와 동일 되도록 문맥이없는 문법이 존재한다.

Answer 2

DFA의 PDA 버전은 각 상태 전환이 스택에 아무 ​​것도 보내지 않고 스택에서 아무 것도 튀지 않는 것을 제외하고는 똑같을 것입니다.

Answer 3

PDA는 단 하나의 추가 기능을 갖춘 DFA의 확장판이므로 스택. DFA의 전환이 튜플 (현재 상태, 입력)에 의해 결정되는 동안 PDA의 전환은 트리플 (현재 상태, 입력, 스택 상단의 요소)에 의해 결정되기 때문에. 유일한 차이점은 스택 맨 위에있는 요소입니다. 당신은 스택

의 상단에있는 요소로 삽입 된 트리플, e (빈 문자열)로 튜플을 변환하여 그리고 상태를 변경 한 후 DFA의 모든 전환을 변환 할 수 있습니다에 e (빈 문자열)을 밀어 스택

Answer 4

다른 사람이 살펴보기 위해이 오래된 질문에 대답하고 있습니다.

DFA와 PDA의 전환은 스택 추가만으로 쉽게 자동화 할 수 있습니다.하지만 DFA의 의미에 변경이있을 수 있으며 수동으로 변경하면 상태 수가 적은 PDA에서 수동으로 끝날 수 있습니다. 나는이 문제에 최근 직면했다. 이것과 다소 비슷합니다.

시스템 (컴파일러가 아니거나 그와 같은 것)에서는 이전에 작성된 코드가 몇 가지 이유로 DFA를 사용하여 작성되었습니다. 전환은 사용자가 다양한 기능을 사용하여 코드를 진행함에 따라 발생합니다. 얼마 후에 새로운 순서의 함수가 도착하여 어떤 순서로든 사용할 수 있습니다. 또한이 새로운 기능들 중 하나가이 기능들 중 하나에 의해 이전 상태로 다시 바뀔 수있는 이후의 상태도 제공됩니다. FST를 사용하여이 문제를 해결할 수있는 유일한 방법은 많은 양의 새로운 상태를 추가하여이 동작을 지원하는 것이 었습니다. 하지만 대신 DFA에서 PDA로 변경했습니다. 스택은 전환을 매우 잘 추적하고 훨씬 적은 수의 상태로 문제를 해결합니다. 실제로 나는 N이 도착한 새로운 함수의 수인 N 개의 상태만을 추가해야했습니다.

누군가 이러한 종류의 프로세스를 쉽게 자동화 할 수 있는지 알 수 없습니다. 그러나 누군가가 그것에 대해 호기심이 생길 때를 대비하여 거기에 있습니다.