일반 언어로 폐쇄

Question

a) $ l $ 정규 언어가되게하십시오.이론에 따르면 언어를 허용하는 DFA가 있습니다.

$ l ^ R $ 을 허용하는 DFA를 NFA로 변경하는 방법을 곧 설명합니다.

공식적으로 또는 증거 또는 정확성을 빌드하는 방법은 없습니다.

b) true 또는 false : $ l $ 이 정기적이지 않은 경우 $ l ^ r $ 규칙적인

가 아닙니다

내 해결책 :

a) 우선, 우리가 수락 상태를 반대로 시작하고 거부 상태가 받아 들일 것이고, 가장자리의 방향을 반전 측으로 변경할 수도 있기 때문에 그러나 NFA IM으로 변경하는 것이 비트 갇혀 있습니다.

b) 정기적으로 $ l ^ r $ 은 정규 일뿐만 아니라 은 A와 B의 방법입니다.

Answer 1

a)

우선, 우리가 수락 상태가 시작될 것이고 거부 상태가 받아 들일 것이고, 가장자리의 방향을 반전 측으로 변경할 수 있기 때문에,

거의 거의 있습니다. 원래 DFA에서 여러 명의 수락 된 주를 수락하면 어떻게됩니까? 이는 NFA 기능이 필요한 곳입니다.

여기에 답변을 확인하려는 경우에는 DFA 설계 및 컴퓨터의 역순을 컴퓨터에 지정합니다. .

b)

당신의 대답은 조금 더 신중하게 문구를 원할 것입니다. 우리는 " $ l $ 이 정기적이지 않습니다. $ l ^ r $ 은 정기적이지 않습니다." ...에 $ l $ 정기적이지 않아야합니다. $ l ^ R $ 이 정기적 이었기 때문에 $ (l ^ r) ^ r= l $ , 모순입니다. 따라서 $ l ^ r $ 은 정기적이지 않습니다.