일반적인 별 높이 문제

정형 언어 이론에서 일반화된 별 높이 문제는 모든 정규 언어가 클린 별의 둥지 깊이가 제한된 일반화된 정규 표현을 사용하여 표현될 수 있는지 여부이다.여기서 일반화된 정규 표현식은 정규 표현식과 같이 정의되지만 보 연산자가 내장되어 있습니다.정규 언어의 경우, 그 일반화 별의 높이는 일반화 정규 표현에 의해 언어를 기술하기 위해 필요한 클린 별의 최소 내포 깊이로 정의되며, 따라서 문제의 명칭이다.

보다 구체적으로 말하면, 1을 넘는 네스트 깊이가 필요한지, 필요한 최소 별 ^[1]높이를 결정하는 알고리즘이 있는지 여부는 미해결의 문제입니다.

별 높이 0의 일반 언어는 별 없는 언어라고도 합니다.Schützenberger의 정리는 무주기 통사적 모노이드를 이용하여 별이 없는 언어의 대수적 특성을 제공한다.특히 별이 없는 언어는 정규 언어의 적절한 결정 가능한 하위 클래스입니다.

「 」를 참조해 주세요.

• 별 높이 기사의 에간 정리 및 일반화된 별 높이 섹션
• 별 높이 문제

레퍼런스

• Janusz A. Brzozowski (1980). "Open problems about regular languages". In Ronald V. Book (ed.). Formal Language Theory: Perspectives and Open Problems. Academic Press. pp. 23–47.
• Wolfgang Thomas (1981). "Remark on the star-height-problem". Theoretical Computer Science. 13 (2): 231–237. doi:10.1016/0304-3975(81)90041-4. MR 0594062.
• Jean-Eric Pin; Howard Straubing; Denis Thérien (1992). "Some results on the generalized star-height problem" (PDF). Information and Computation. 101 (2): 219–250. doi:10.1016/0890-5401(92)90063-L.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups". Information and Control. 8 (2): 190–194. doi:10.1016/S0019-9958(65)90108-7. Zbl 0131.02001.

외부 링크

• Jean-Eric 핀:별 높이 문제