나는

2010-03-22 11 views
-6

이 나에게 다음과 같은 언어를 결정하는 문법 또는 자동 장치를 찾을 수 있도록 도와주십시오이 언어에 대한 자동 장치를 찾을 필요가 :나는

N B N C를 N 곳 n≥1

+3

숙제? _____ – kennytm

+0

..... 숙제? –

+0

............. 숙제? – Fabian

답변

4

이 언어는 pumping lemma for context-free languages (사실이 언어는 CFL 펌프 보조 정리의 예제로 사용됨) 오류가 발생하지 않으므로 일반 언어 나 문맥이없는 언어가 아닙니다. 가장 좋은 방법은 튜링 기계를 사용하는 것입니다.

분명히 결정적인 언어입니다. 사용하고자하는 오토 마톤의 유형을 잘 알고 있으면 스스로 문제를 찾을 수 있습니다. 이 모양이 숙제와 같아서 그 단서가 당신에게 줄 것입니다.