CFG 언어와 일반 언어의 교차점 계산 ∑ki=0A케이

$\sum_{i=0}^k A^k$ (이것은 상태 수에 케이

$k$“데드 엔드”상태 추가). 이제 결과가 비어 있는지 확인하십시오. 문법으로 변환하십시오 (결과는 다항식 크기를 가질 것이라고 생각합니다).

편집 : Kaveh는 다항식이라고 언급했습니다. 케이

$k$, 그래서 만약 케이

$k$ 입력으로 주어지면 알고리즘은 지수 | k |

$|k|$. 그러나 Kaveh는이 문제를 해결하는 방법을 찾았습니다. 원래 오토 마톤을 CFG로 변환하고 모든 터미널을 고정 터미널로 교체하십시오. 이제 반복 알고리즘을 사용하여 다음과 같이 각 비 터미널에 의해 생성 된 단어의 최소 크기를 찾으십시오.

로 모든 길이를 초기화 ∞

$\infty$그런 다음 명백한 방식으로 모든 길이를 반복적으로 업데이트하십시오. A →ㅏ티∏비나는

$A \rightarrow a^t \prod B_i$ (순서는 중요하지 않습니다) 에프( A ) = 최소 (f( A ) , t + ∑ f(비나는) )

$f(A) = \min(f(A),t+\sum f(B_i))$. 주장 : 이것은O ( n )

$O(n)$ 반복 엔

$n$비 터미널의 수입니다. 그 이유는 최소 길이 단어를 생성하는 트리에서 비 터미널이 두 번 사용되지 않기 때문입니다. 각 “가장자리”는 처리하는 데 최대 하나의 반복이 필요합니다 (일부 가장자리는 병렬로 “업데이트”될 수 있음).

답변