بترکه چشم حسود    

جستجوی پیشرفته مقالات

     عنوان:

نماد اعتماد الکترونیکی

logo-samandehi

لیست مقالات ترجمه شده

سایر مقالات

امروز
دیروز
هفته جاری
هفته گذشته
ماه جاری
ماه گذشته
بازدید کل
2679
2620
7453
4382061
46010
79496
4667296

آی‌پی شما: 54.163.20.57
امروز: سه شنبه، 22 آبان 1397 شمسی ساعت به وقت گرینویچ: 21:08:21

توجه                           توجه

تمامی مقالات ترجمه شده در قالب فایل ورد (Word)  ارائه می‌شوند.



مکمل روی زبان های NFA بدون پیشوند، بدون پسوند و غیربازگشتی

لینک دانلود فایل خریداری شده، بلافاصله بعد از پرداخت آنلاین فعال می‌شود.

عنوان محصول:
مکمل روی زبان های NFA بدون پیشوند، بدون پسوند و غیربازگشتی



قیمت: 180000 ریال

  دسته‌بندی: مقالات نظریه ماشین

Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages

Abstract

We prove that the tight bound on the nondeterministic state complexity of complementation on prefix-free and suffix-free languages is 2n−1. To prove tightness, we use a ternary alphabet, and we show that this bound cannot be met by any binary prefix-free language. On nonreturning languages, the upper bound is 2n−1 +1, and it is tight already in the binary case. We also study the unary case in all three classes.

 

pdfدانلود رایگان مقاله انگلیسی           975.06 KB

چکیده

ثابت می کنیم که کران سخت روی پیچیدگی حالت غیرقطعی مکنل روی زبان های بدون پیشوند و پسوند برابر 2n-1 است. برای اثبات سختی از الفبای سه تایی استفاده می کنیم و نشان می دهیم که این کران (حد) نمی تواند توسط هر زبان بدون پیشوند باینری برقرار باشد. در زبان های غیربازگشتی، کران بالا برابر 2n-1+1 است و در حالت باینری، سخت است. همچنین به مطالعه مورد یکانی در هر سه دسته می پردازیم.

 

تعداد صفحات مقاله انگلیسی:12 صفحه
تعداد صفحات مقاله فارسی: 20 صفحه
نوع فایل: ورد

اضافه کردن نظر


کد امنیتی
تازه سازی