کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950575 1440713 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Information rate of some classes of non-regular languages: An automata-theoretic approach
ترجمه فارسی عنوان
نرخ اطلاعات برخی از کلاس های زبان های غیر منظم: یک روش اتوماتیک-نظری
کلمات کلیدی
خودکار زبان رسمی، اطلاعات شانون،
ترجمه چکیده
ما نشان می دهیم که میزان اطلاعات زبان پذیرفته شده توسط ماشین حساب شمارنده قطعی معکوس محاسبه می شود. برای موارد غیرتمرینتی، ما مرزهای بالایی قابل محاسبه را ارائه می دهیم. برای کلاس زبان های پذیرفته شده توسط ماشین های اتوماتیک قطعی قطعی چند نوار، میزان اطلاعات نیز قابل محاسبه است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
نرخ اطلاعات برخی از کلاس های زبان های غیر منظم: یک روش اتوماتیک-نظری
چکیده انگلیسی
We show that the information rate of the language accepted by a reversal-bounded deterministic counter machine is computable. For the nondeterministic case, we provide computable upper bounds. For the class of languages accepted by multi-tape deterministic finite automata, the information rate is computable as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 45-61
نویسندگان
, , , ,