나는 혼란스럽고 온라인에서 답을 찾을 수 없지만 표현력면에서 보면 과 같다.FA의 결정 론적 표현력과 결정 론적 표현력을 비교하면, PDA와 TM 'S
비결정 FA, PDA, TM
NFA < NPDA < NTM
결정적 FA, PDA, TM : 이것은 전체에서
DFA < PDA < TM?
혼란 어딘지이다 :
DFA = NFA = e-NFA = RE < DPDA < NPDA = NCFL = DCFL < NTM = DTM?
수정 하시겠습니까? 아니면 올바르게 입력 했습니까?
DFA < PDA < TM이 맞습니다.
DFA = NFA = RegEx로만 저장하면 모든 NFA를 RegEx로 변환 할 수있는 DFA로 변환 할 수 있으며 그 반대의 경우도 있습니다.
컨텍스트 무료 언어는 약간 다릅니다. PDA ≠ NPDA. 컨텍스트가없는 언어의 하위 집합에 대해 PDA를 만들 수 있지만 모든 컨텍스트가없는 언어에 대해 NPDA를 구성 할 수 있습니다.
결정적이며 비 결정적 인 튜링 기계는 똑같이 강력합니다. 단일 테이프 DTM을 사용하여 모든 NTM을 시뮬레이션 할 수 있다는 것을 기억하십시오. 그래서 전부
, DFA = NFA = 전자 NFA = < DPDA < NPDA = NCFL = DCFL < NTM RE = DTM 올바른 직관이다.
@sungyong 편집을 해주셔서 감사합니다.] –
NCFL과 DCFL이 무슨 뜻인지 잘 모르겠지만 그 중 두 가지를 "CFG"로 바꾸면 올바른 것입니다. ='는''와 같이 강력 함을 의미하고''는''덜 강력합니다 '를 의미합니다. – Patrick87