نظرية الحوسبة

نظرية الحوسبة
صممت الحسابات لحل المشاكل ، صممت الحسابات لمعالجة المعلومات وهذه الحسابات يمكن ان تكون بسيطة مثل تقدير وقت القيادة بين المدن ومعقدة مثل التنبؤ بالطقس.

الاحرف الابجدية والنصوص
القدرة على تمثيل المعلومات هو امر حاسم في التواصل ومعالجة المعلومات أنشأت المجتمعات البشرية اللغات المنطوقة للتواصل على المستوى الأساسي ، وطورت الكتابة للوصول إلى مستوى أكثر تطوراً.
تعتمد اللغة الإنجليزية ، على سبيل المثال ، في شكلها المنطوق على مجموعة محدودة من الأصوات الأساسية كمجموعة من الأوليات. يتم تعريف الكلمات على انها مجموعة متتابعات محددة من هذه الأصوات. والجمل مشتقة من متتابعات محدودة من الكلمات. يتم إجراء المحادثات من سلسلة متتابعة من الجمل وما إلى ذلك.
تستخدم اللغة الإنجليزية المكتوبة مجموعة من الرموز المحدودة كمجموعة من المتتابعات. يتم تعريف الكلمات من خلال متتابعات محدودة من الرموز. الجمل مشتقة من متتابعات محدودة من الكلمات. يتم الحصول على الفقرات من تتابعات الجمل المحددة وما إلى ذلك.
تم تطوير أساليب مماثلة أيضًا لتمثيل عناصر من مجموعات أخرى. على سبيل المثال ، يمكن تمثيل العدد الطبيعي بتتابعات محدودة من الأرقام العشرية.
ومن المتوقع أن تتعامل الحسابات ، مثل اللغات الطبيعية ، مع المعلومات في شكلها الأكثر عمومية. القدرة على تمثيل المعلومات أمر بالغ الأهمية لتوصيل المعلومات ومعالجتها للوصول إلى مستوى أكثر تطوراً ، ومن المتوقع أن تتعامل مع المعلومات في شكلها العام وما إلى ذلك
تسمى مجموعة منتهية غير محددة فارغة بالحروف الأبجدية (سكما) ? إذا كانت عناصرها عبارة عن رموز أو أحرف. والتسلسل المحدود من الرموز من الأبجدية المعينة ستسمى سلسلة من الأبجدية. تشير بعض الكتب إلى الجمل او السلاسل على أنها كلمات فقط إذا تحدثت عن سلاسل متضمنة بلغة معينة. بعض الناس (وأنا منهم) لا يقومون بالضرورة بهذا التمييز.
سلسلة تتكون من تسلسل a1 ، a2 ،. . . ، رمزا من الرموز سوف يرمز لها من جانب a1a2..an. السلاسل التي لها رموز صفرية تسمى السلاسل الفارغة ، سيتم الرمز إليها بـ ?.

مثال: ?1 = {a, . . . , z} و ?2 = {0, . . . , 9} هي حروف ابجدية ، abb هو سلسلة من ?1و 123 هو سلسلة من ?2 . ba12 ليست ضمن ?1 لانها تحتوي رموز غير موجودة في ?1 وكذلك 314.. ليس ضمن ?2 لانه ليس تسلسلا محدودا ، من جانب اخر فان ? تعتبر جزء او سلسلة عبر اي ابجدية.
المجموعة الخالية ? لاتعتبر ابجدية لانها لاتحتوي على عناصر مجموعة الأعداد الطبيعية ليست أبجدية ، لأنها ليست محدودة. الاتحاد ?1? ?2 يعتبر ابجدية فقط اذا تم وضع ترتيب على رموزه .
تسمى الابجدية التي تتكون من اصل2 بالابجدية الثنائية وتسمى السلاسل في الأبجدية الثنائية بالسلاسل الثنائية. وبالمثل ، تُعرف أبجدية من أصل 1 بالأبجدية الأحادية ، وتسمى السلاسل في الأبجدية الأحادية بالسلاسل الأحادية.
طول السلسلة ? يرمز له |?|ويفترض ان يساوي عدد الرموز في السلسلة
مثال: {0,1} هي ابجدية ثنائية و {1} هي ابجدية احادية .11 هي سلسلة ثنائية عبر الابجدية {0,1} وسلسلة احادية عبر الابجدية {1}.
11 هي سلسلها طولها2 | ?| = 0 و |01| + |1| = 3
السلسلة التي تتكون من تتابع ? متبوعة بتتابع ? يشار لها ب ?? ، تسمى هذه السلسة بتسلسل او تجميع ? و ? . يتم الرمز ?i للسلسلة التي تم الحصول عليها عن طريق تجميع عدد معين (i) من نسخ السلسلة
مثال: تجميع السلسلة01 مع السلسلة 100 تعطي السلسلة 01100 ، اذا ? = 01 فان ?0 =? , ?1 = 01, ?2 = 0101 و ?3 = 010101
اللغات الرسمية
إن عالم السلاسل هو وسيط مفيد لعرض المعلومات طالما أن هناك وظيفة توفر تفسيرًا للمعلومات التي تحملها السلاسل. التفسير هو عكس المعادلة التي يقدمها التمثيل ، أي أن التفسير هو دالة g من ?*إلى D لبعض الأبجدية ? وبعضها D. يمكن تفسير السلسلة 111 ، على سبيل المثال ، على أنها الرقم مائة وأحد عشر ممثلة بسلسلة عشرية ، كعدد سبعة ممثلة في سلسلة ثنائية ، والرقم الثلاث الذي يمثله سلسلة أحادية. يقوم الطرفان بتوصيل جزء من المعلومات بالتمثيل والتفسير. يتم توفير التمثيل من قبل المرسل ، ويتم توفير التفسير من قبل المتلقي. العملية هي نفسها بغض النظر عما إذا كانت الأطراف هي بشر أو برامج. وبالتالي ، من وجهة نظر الأطراف المعنية ، يمكن أن تكون اللغة مجرد مجموعة من الأوتار لأن الأطراف تضمّن وظائف التمثيل والتفسير في ذاتها.
بشكل عام ، إذا كانت الأبجدية ? و L هي مجموعة فرعية من ?*، عندئذٍ يُقال أن L هي لغة ضمن ? ، أو لغة بسيطة إذا تم فهم ?. يقال إن كل عنصر من عناصر L هو عبارة عن جملة أو كلمة أو سلسلة من اللغة.
مثال: {0, 11, 001}, {? , 10} و {0, 1}* هي اجزاء من {0, 1}* وبالتالي فهي لغات ابجدية {0, 1} المجموعة الخالية ? والمجموعة {? } هي لغات ضمن الابجدية ، ? هي لغة لاتحتوي على اي سلسلة ، ?}} هي لغة تحتوي على السلسلة الفارغة فقط.
يشير اتحاد اللغتين L1 و L2 ، المشار إليهما L1 L2 ، إلى اللغة التي تتكون من جميع السلاسل التي تكون إما في L1 أو L2 ، أي إلى {x | x في L1 أو x في L2}
يشير تقاطع L1 و L2 ، المشار إلى L1 L2 ، إلى اللغة التي تتكون من جميع السلاسل الموجودة في كل من L1 و L2 ، أي إلى {x | x في L1 وفي L2}.
المتتمة للغة L خلال ? او مجرد متممة ال L عندما تفهم . يرمز L- للغة التي تحتوي كل السلاسل ضمن ? لكنها غير متواجدة ضمن L أي إلى {x | x في ?* ولكن ليس في L}.
مثال: خذ بنظر الاعتبار اللغات L1 = {? , 0, 1} و L2 = { ?, 01, 11} اتحاد هذه اللغات هو L1? L2 = {? , 0, 1, 01, 11} وتقاطعها هو L1 ? L2 = {? } ومتممة ال L1 هو = {00, 01, 10, 11, 000, 001, . . . }