2
문맥 자유 문법을 DFA로 변환하는 방법? 만약 우리가 A-> a B와 같은 천이를하면 이것은 쉽습니다. 그러나 A-> a Bc로 천이했을 때. 그런 다음 DFA로 표현하는 방법오토마타 이론 : 문맥 자유 문법을 DFA로 변환
A
답변
0
먼저 언어를 CNF (Chomskey Normal Form)으로 변환해야합니다. 그런 다음 변환을위한 단계는 다음과 같은 수 있습니다 :
정규 문법이라고 좌/문법을 왼쪽으로 변환합니다. 모든 제품 A의 다음과 같이 오토마타위한
Convert the Regular Grammar into Finite Automata 트랜지션이 얻어 -> AB 만들 δ (A는 a) 할 것이다 B를 =에 '은'모든 제조 B. A에서 분류되고 A -> a는 δ (A, a) = 최종 상태를 만든다. 모든 생산 A -> ε에 대해 δ (A, ε) = A를 만들고 A가 최종 상태가됩니다.
CFG를 항상 DFA로 변환 할 수있는 것은 아니지만 예 왼쪽 또는 오른쪽 선형이면 가능합니다. 이 경우이 대답은 도움이 될 수 있습니다 [왼쪽 선형 및 오른쪽 선형 그래머] (http://stackoverflow.com/questions/13816439/left-linear-and-right-linear-grammars/13945932#13945932) –
A-> a B c를 위해 우리는 dfa를 구성 할 수 없다 ?? – bulbasaur
먼저 문법을 왼쪽 또는 오른쪽으로 변환 한 다음 DFA를 그려야합니다. CFG를 왼쪽 선형 (오른쪽 라이너)으로 변환 할 수없는 경우 실제 문법은 정규 언어의 수퍼 세트 인 CFL을 생성하고 CFL 용 DFA는 불가능합니다. 'A -> a B c' 오직 하나의 프로덕션 규칙 (문법이 아님) 때문에 queston이 이해할 수 없습니다 –