زبان های صوری

در ریاضیات، منطق و علوم کامپوتر، زبان صوری یک مجموعه از کلمات (رشته های کاراکتری) با طول متناهی  است که از برخی الفباهای متناهی مشتق می گردد، و نظریه علمی که مرتبط با این مفاهیم است  به عنوان نظریه زبان صوری شناخته می شود.

یک الفبا ممکن است {a,b} ،و رشته بر روی آن ababba باشد.یک زبان نمونه بر روی این الفبا، که دارای رشته عنوان شده است، ممکن است مجموعه تمام رشته های باشد که شامل علائم a و b با تعداد مساوی است.

رشته تهی (رشتهای با طول صفر) رشته با معنا تلقی می گردد و با علامe, ε, Λ. نمایش داده می شود. از آن جایی که الفبا یک مجموعه متناهی است وهر عبارت دارای طول محدود است، زبان ممکن است دارای رشته های عضو نامحدود باشد.

سوالی که اغلب در مورد زبان های صوری پرسیده می شود این است "  آیا یک عبارت داده شده به زبان تعلق دارد یا خیر؟" ، که جواب آن، بحث مورد برسی نظریه محاسبات و نظریه پیچیدگی است

چند مثال از زبان های صوری:

1-     مجموعه رشته های تولید شده بر روی a و b .

2-     مجموعه {a^n}،n یک عدد اول است.

3-     زبانی متناهی مانند a،aa،bba .

4-     مجموعای از برنامه های یک زبان برنامه نویسی که از نظر نحوی صحیح می باشند.

5-     مجموعای از ورودی ها که ماشین تورینگ خاصی بر روی آن متوقف می گردد.

یک زبان صوری به وسیله راه های مختلفی مشخص می گردد، از جمله:

1-     رشته هایی که توسط گرام های صوری تولید می شوند.

2-     رشته هایی که توسط عبارات منظم تولید می شوند

3-     رشته هایی که توسط برخی ماشین ها، مانند ماشین تورینگ یا ماشین حالت متناهی پذیرفته می شوند.

4-     آن دسته از سوالات بله/ خیر که جوابشان بله است.

http://en.wikipedia.org/wiki/Formal_language