3
는
(내가 대답을 발견, 그 아래에 다른 사람을위한 주석)시간 복잡도 무역 오프는
내가있는 더 나은 사용하고 컴파일러에서 무엇을 circumstanes NFA 또는 토론을 찾고 있어요 dfa. nfa 대 dfa를 시뮬 레이팅하는 시간 복잡성 거래는 무엇이고 컴파일러에서 어떤 상황에서 더 적합합니까 ??
은 대학 시험에 도움을 개정 메신저 크게 apriciated 될 것입니다 감사합니다 :)리앤을. 누군가가 나에게 대답 : (
을 간단한 아이디어를 줄 수 있습니다 (더 내다 없다고 가정, 그것은 그래서 막 다른 골목으로 실행되는 다음 문자가 될 것입니다 무엇을 알고하지 않습니다) 나는 다른 사람이 .. – user560618
를 찾고에 대한 답을 발견 시간 - 공간 트레이드 오프 목표 : 주어진 reg. exp.r과 input stringx, Lx에 있는지의 여부를 결정한다. Method # 1 : Thompson의 구조를 사용하여 NFAN fromr을 구축하고 이전 알고리즘을 실행한다. NFA inO (| r |) 시간을 구성 할 수있다. ¡ N은 | r |의 두 배만큼 많은 상태를 가지며 각 상태에서 최대 두 개의 전환이 있으므로 전환 표는 | (| r |) 공간입니다. ¡ 이전 알고리즘이 허용하거나 거부하는 inO (| r | × | x |) 시간 – user560618
방법 2 : Thompson의 구조를 사용하여 NFAN fromr을 만든 다음 하위 집합 구성을 사용하여 N 의 DFAD를 작성합니다. 마지막으로 수락/거절에 대한 을 사용하십시오. ¡ D는 최대 2k 개의 상태를 가질 수 있습니다. 여기서 k는 N의 상태를 나타냅니다. '최악의 경우' '문자열 (a | b) * a (a | b) (a | b) ... (a | b) : 왜? (x |) – user560618