Ordinary Generating Functions of Context-Free Grammars

دسته بندی: منطق
ویرایش:  
نویسندگان: Swett T.,  Aboufadel E.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 13 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 280 کیلوبایت 

قیمت کتاب (تومان) : 35,000

ایالات متحده آمریکا: دانشگاه ایالتی گراند ولی (GVSU). - 1393. گروه ریاضی. تحقیقات کارشناسی. مقاله 3، ص: 1-12، انگلیسی. مقدمه
گرامر بدون متن یک ساختار ریاضی است که طبقه بندی می کند رشته‌ها (توالی نمادها) به‌عنوان \"معتبر\" یا \"نامعتبر\"، با تعیین مجموعه‌ای از \"قوانین تولید\" که روش‌های تشکیل رشته‌های معتبر را تعیین می‌کنند. یک \"زبان\" (یعنی مجموعه‌ای از رشته‌ها) که توسط یک دستور زبان بدون متن ایجاد می‌شود، به عنوان یک زبان بدون متن شناخته می‌شود.
اگرچه گرامرهای بدون متن در ابتدا برای مطالعه زبان انسان مورد استفاده قرار می‌گرفتند، این مقاله زبان های عاری از زمینه را در زمینه نظری تر بررسی می کند. به طور خاص، ما به \"شمارش دنباله‌ها\" علاقه‌مندیم: با توجه به یک زبان، دنباله شمارش آن دنباله‌ای از اعداد طبیعی است که بیان می‌کند چند رشته از هر طول عناصر زبان هستند.
تابع تولید معمولی یک دنباله سری توانی است که ضرایب آن عناصر دنباله است. این مقاله به بررسی ویژگی‌های توابع مولد معمولی شمارش دنباله‌های زبان‌های بدون بافت می‌پردازد.
ما با تعریف یک دستور زبان بدون بافت و یک تابع تولید معمولی و بحث در مورد چند مثال شروع می‌کنیم. سپس در مورد قضیه چامسکی-ش utzenberger بحث خواهیم کرد، قضیه ای مهم در مورد توابع مولد زبان های بدون بافت.
در نهایت، ما مفهوم گرامر بدون متن را با تعریف گرامرهای بدون متن با اعداد صحیح گسترش خواهیم داد، که در آن هر قانون دارای یک برچسب (احتمالاً منفی) است که نشان دهنده تعدد آن قانون است. ما ثابت خواهیم کرد که یک نسخه توسعه‌یافته از قضیه چامسکی-ش utzenberger برای گرامرهای بدون متن با برچسب صحیح نیز صادق است. محتوا.< br/>1 مقدمه.
2 گرامرهای بدون زمینه و توابع تولید آنها.
گرامرهای بدون متن.
تولید توابع برای گرامرهای بدون متن.
مثال: زبانی از Du & Ko.
زبان Dyck.
قضیه چامسکی{Sch utzenberger.
نمونه‌هایی از Flajolet.
3 گرامر بدون متن دارای برچسب عدد صحیح.
تعریف.
نمونه ای از Du & Ko مورد بازبینی مجدد قرار گرفت.
قدرت nilCFGs؟ .
قضیه چامسکی{Sch utzenberger، توسعه یافته.
قدردانی.

USA.: Grand Valley State University (GVSU). - 2014. Mathematics Department. Undergraduate Research. Paper 3, P.p.: 1-12, English. Introduction
A context-free grammar is a mathematical construct that classifies strings (sequences of symbols) as either "valid" or "invalid", by specifying a set of "production rules" which determine the ways in which valid strings can be formed. A "language" (that is, a set of strings) generated by a context-free grammar is known as a context-free language.
Although context-free grammars were initially used to study human language, this paper investigates context-free languages in a more theoretical context. Specifically, we are interested in "counting sequences": given a language, its counting sequence is a sequence of natural numbers stating how many strings of each length are elements of the language.
The ordinary generating function of a sequence is the power series whose coefficients are the elements of the sequence. This paper investigates the properties of ordinary generating functions of counting sequences of context-free languages.
We will begin by de ning a context-free grammar and an ordinary generating function, and discussing some examples. We will then discuss the Chomsky-Schutzenberger Theorem, an important theorem about the generating functions of context-free languages.
Finally, we will extend the notion of a context-free grammar by de ning integer-labeled context-free grammars, where each rule has a (possibly negative) label indicating the multiplicity of that rule. We will prove that an extended version of the Chomsky-Schutzenberger Theorem also holds for integerlabeled context-free grammars. Contents.
1 Introduction.
2 Context-free grammars and their generating functions.
Context-free grammars.
Generating functions for context-free grammars.
Example: a language from Du & Ko.
The Dyck language.
The Chomsky{Schutzenberger Theorem.
Examples from Flajolet.
3 Integer-labeled context-free grammars.
De nitions.
Example from Du & Ko revisited.
The power of nilCFGs? .
Chomsky{Schutzenberger Theorem, extended.
Acknowledgements.