نظریه زبانها: تفاوت میان نسخهها
جز روبات: اِعمال دستور خط فارسی و فرهنگ املایی |
AlleborgoBot (بحث | مشارکتها) جز ربات افزودن: hi:औपचारिक भाषा |
||
خط ۴۹: | خط ۴۹: | ||
[[ar:لغة شكلية]] |
[[ar:لغة شكلية]] |
||
⚫ | |||
[[bg:Формален език]] |
[[bg:Формален език]] |
||
⚫ | |||
[[cs:Formální jazyk]] |
[[cs:Formální jazyk]] |
||
[[da:Formelt sprog]] |
[[da:Formelt sprog]] |
||
[[de:Formale Sprache]] |
[[de:Formale Sprache]] |
||
[[el:Τυπική γλώσσα]] |
[[el:Τυπική γλώσσα]] |
||
[[en: |
[[en:Formal language]] |
||
[[es:Lenguaje formal]] |
[[es:Lenguaje formal]] |
||
⚫ | |||
[[fr:Langage formel]] |
[[fr:Langage formel]] |
||
⚫ | |||
⚫ | |||
⚫ | |||
[[he:שפה פורמלית]] |
[[he:שפה פורמלית]] |
||
[[hi:औपचारिक भाषा]] |
|||
⚫ | |||
[[hu:Formális nyelv]] |
[[hu:Formális nyelv]] |
||
⚫ | |||
⚫ | |||
⚫ | |||
[[mk:Формален јазик]] |
[[mk:Формален јазик]] |
||
[[nl:Formele taal]] |
[[nl:Formele taal]] |
||
⚫ | |||
[[pl:Język formalny]] |
[[pl:Język formalny]] |
||
[[pt:Linguagem formal]] |
[[pt:Linguagem formal]] |
||
خط ۷۲: | خط ۷۴: | ||
[[simple:Formal language]] |
[[simple:Formal language]] |
||
[[sk:Formálny jazyk]] |
[[sk:Formálny jazyk]] |
||
⚫ | |||
[[tr:Biçimsel dil kuramı]] |
[[tr:Biçimsel dil kuramı]] |
||
[[uk:Формальна мова]] |
[[uk:Формальна мова]] |
نسخهٔ ۲۷ ژوئن ۲۰۰۸، ساعت ۱۲:۰۱
در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمولهای دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شداند، زبانهای فُرمال گفته میشود.
به طور کلی در این رشتهها، زبان ها به دو دسته فرمال و طبیعی تقسیم بندی می شوند . زبان های فرمال زبان هایی هستند که توسط گرامر ها تولید می شوند یا ماشینی برای ارزبابی آنها وجود دارد .
تعاریف پایه
- نماد : کوچک ترین و بنیادی ترین عضو یک زبان است . برخی مواقع به نماد ها حرف هم گفته می شود . نماد ها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان می دهند .
- الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده اند . الفبای زبان توسط Σ نشان داده می شود .
- رشته : دنباله ای از نماد های یک مجموعه الفباست که با عمل الحاق به هم پیوسته اند .
رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می دهند . طول رشته را با قدر مطلق آن نمایش می دهند . مثلاً :
اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است .
- زبان : مجموعه ای از رشته ها است . این مجموعه می تواند متناهی ، نامتناهی شمارا یا نامتناهی ناشمارا باشد .
زبان بدون رشته را با Ø نشان می دهند .
رشته ای به طول صفر را با λ یا ε نشان می دهند . آن را رشته تهی می نامند .
دستهبندی زبانهای فرمال
زبان های فرمال به چهار دسته تقسیم می شوند :
عملگرهای روی زبان های فرمال
زبان مجموعه ای از رشته هاست . بنابر این ماهیت زبان ها ، مجموعه است . همه عملگر هایی که روی مجموعه ها تعریف شده اند مانند اجتماع ، اشتراک ، متمم ، تفاضل و ... روی زبان ها قابل تعریف هستند .
عملگر الحاق که روی رشته ها تعریف شده است ، روی زبان ها نیز قابل تعریف است .
عملگرهای دیگری مانند عمل معکوس سازی ( Reverse ) نیز روی رشته های زبان قابل تعریف است .
منابع
An Introduction to Formal Languages and Automata, Peter Linz