همنهشتی های فازی مایهیل- نرود متناظر با اتوماتای فازی عمومی
الموضوعات :
خدیجه ابول پور
1
,
محمد مهدی زاهدی
2
,
مرضیه شمسی زاده
3
1 - گروه ریاضی، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران
2 - گروه ریاضی، دانشگاه صنعتی و فناوری پیشرفته کرمان، کرمان، ایران
3 - گروه ریاضی، دانشگاه صنعتی و فناوری پیشرفته کرمان، کرمان، ایران
الکلمات المفتاحية: General fuzzy automata, Monoid, Crisp, Congruence (Myhill-Nerode), Lattice,
ملخص المقالة :
قضیه‌ی مایهیل- نرود یکی از قضایای اساسی در نظریه‌ی زبان‌ها و اتوماتا است و برای اثبات هم‌ارزی اتوماتاها و زبان‌های آنها استفاده می‌شود. اهمیت این قضیه موجب شده تا پژوهشگران تلاش نمایند آن را روی اتوماتا‌های مختلف گسترش دهند و به نوعی در زمینه‌ی بهینه سازی مدل‌های محاسباتی گام بردارند. در این مقاله، به توسعه‌ی مفهوم همنهشتی در اتوماتای فازی عمومی بر پایه‌ی این قضیه می‌پردازیم. بدین منظور، ابتدا با استفاده از مفهوم همنهشتی راست فازی روی یک تکواره‌ی آزاد، اتوماتای فازی عمومی القا شده توسط همنهشتی راست فازی را تعریف می‌کنیم. در ادامه، با استفاده از مفهوم زبان شناسایی شده توسط یک اتوماتا، نشان می‌دهیم که در این اتوماتای القا شده یک زبان قابل شناسایی است، اگر و تنها اگر توسیعی از همنهشتی راست فازی روی تکواره‌ی آزاد باشد. در نتیجه، این زبان شناسایی شده با زبان بخش صریح اتوماتای فوق یکسان است. همچنین، همنهشتی راست فازی نرود و همنهشتی فازی مایهیل متناظر با یک اتوماتای فازی عمومی ماگزیمال-مینیمال را تعریف می‌کنیم و نشان می‌دهیم زبان شناسایی شده بوسیله‌ی اتوماتای فازی عمومی ماگزیمال-مینیمال با زبان شناسایی شده بوسیله‌ی اتوماتای فازی عمومی ماگزیمال-مینیمال القا شده توسط همنهشتی راست فازی نرود یکسان است. در پایان، با ارائه‌ی مثال‌هایی مفاهیم فوق را روشن می‌سازیم.
[1] Abolpour Kh., Zahedi M. M., "Isomorphism between two BL-general fuzzy automata", Soft Computing, 16 (2012) 729-736.
[2] Abolpour Kh., Zahedi M. M., "BL-general fuzzy automata and accept behavior",Journal of Applied Mathematics and Computing, 38 (2012) 103-118.
[3] Abolpour K., Zahedi M. M., "General Fuzzy Automata Based on Complete Residuated Lattice-Valued", Iranian Journal of Fuzzy Systems, 14 (2017) 103-121.
[4] Doostfatemeh M., Kremer S.C., "New directions in fuzzy automata", International Journal of Approximate Reasoning, 38 (2005) 175-214.
[5] Ignjatovic J., Ciric M., Bogdanovic S., Petkovic T., "Myhill-Nerode type theory for fuzzy languages and automata", Fuzzy Sets and Systems, (2009) 1-37.
[6] Maletti A., "Myhill-Nerode theorem for recognizable tree series revisited", in: E. S. Laber, et al. (Eds.) LATIN 2008, Lecture Notes in Computer Science, Vol. 4957, Springer, Heidelberg, 2008, pp. 106-120.
[7] Mordeson J.N., Malik D.S., "Fuzzy Automata and Languages, Theory and Applications", Chapman and Hall/CRC, London/Boca Raton, FL, 2002.
[8] Mordeson J.N., Nair P.S., "Fuzzy Mathematics, An Introduction for engineers and scientists", translated by R. Ameri, university of Mazandaran, Iran, 2003.
[9] Myhill J., "Finite automata and the representation of events", in: WADD TR-57-624, Wright Patterson AFB, Ohio, pp. 112-137.
[10] Nerode A., "Linear automata transformation", in: Proc. American Mathematical Society, Vol. 9, 1958, pp. 541-544.
[11] Santos E. S., "Fuzzy Automata and Languages, Information Sciences", 10 (1976) 193-197.
[12] Shamsizadeh M., Zahedi M. M., Abolpour Kh., "Admissible partition for Bl-general fuzzy automaton", Iranian Journal of Fuzzy Systems, In Press.
[13] Shamsizadeh M., Zahedi M. M., Abolpour Kh., "Bisimulation for BL-general fuzzy automata", Iranian Journal of Fuzzy Systems, 13 (2016) 35-50.
[14] Steinby M., "Classifying regular languages by their syntactic algebras", in: Results and Trends in Theoretical Computer Science, Graz, 1994, Lecture Notes in Computer Sciences, Vol. 812, Springer, Berlin, 1994, pp. 396-409.
[15] Wee W.G., "On generalization of adaptive algorithm and application of the fuzzy sets concept to pattern classification", Ph.D. Thesis, Purdue University, Lafayette, IN, 1967.
[16] Zadeh L .A., "Fuzzy sets", Inform. and Control, 8 (1965) 338-353.
[17] Zahedi M. M., Horry M., Abolpor Kh., "Bifuzzy (General) Topology on Max-Min General Fuzzy Automata ", Advances in Fuzz y Mathematics, Vol. 3, No. 1, (2008), 51-68.
