Learning Automata theory - Informatics - Lesson 1 - Introduction

Informatics is the study of the structure, behaviour, and interactions of natural and engineered computational systems. Informatics studies the representation, processing, and communication of information in natural and engineered systems. It has computational, cognitive and social aspects.

An automaton is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions

Informatics has many aspects, and encompasses a number of existing academic disciplines - Artificial Intelligence, Cognitive Science and Computer Science.

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.

Automata theory is closely related to formal language theory. In this context, automata are used as finite representations of formal languages that may be infinite. Automata are often classified by the class of formal languages they can recognize, as in the Chomsky hierarchy, which describes a nesting relationship between major classes of automata. Automata play a major role in the theory of computation, compiler construction, artificial intelligence, parsing and formal verification.

Turing machines, first described by Alan Turing in Turing 1936–7, are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed. Turing's 'automatic machines', as he termed them in 1936, were specifically devised for the computing of real numbers.


نظرية الأوتوماتا - اللغات الصورية - المعلوماتية - الدرس الأول - المقدمة

المعلوماتية هي دراسة بنية وسلوك وتفاعلات الأنظمة الحسابية الطبيعية والمُهندَسة. تدرس المعلوماتية تمثيل المعلومات ومعالجتها وإيصالها في الأنظمة الطبيعية والهندسية. لها جوانب حسابية ومعرفية واجتماعية.

الأوتوماتون عبارة عن آلة ذاتية التشغيل نسبيًا ، أو آلية تحكم مصممة لتتبع سلسلة من العمليات تلقائيًا ، أو الاستجابة لتعليمات محددة مسبقًا

المعلوماتية لها جوانب عديدة ، وتشمل عددًا من التخصصات الأكاديمية الحالية - الذكاء الاصطناعي والعلوم المعرفية وعلوم الكمبيوتر.

نظرية الأوتوماتا هي دراسة الآلات المجردة والأوتوماتا ، بالإضافة إلى المشكلات الحسابية التي يمكن حلها باستخدامها. إنها نظرية في علوم الكمبيوتر النظرية. تأتي كلمة الأوتوماتا من الكلمة اليونانية αὐτόματος ، والتي تعني "ذاتية التصرف ، وذاتية الإرادة ، وذاتية الحركة". الآلي (الأوتوماتا بصيغة الجمع) هو جهاز حوسبة ذاتية الدفع مجردة يتبع تسلسل محدد مسبقًا من العمليات تلقائيًا. يُطلق على الإنسان الآلي الذي يحتوي على عدد محدود من الحالات اسم أوتوماتيكي محدود (FA) أو آلة الحالة المحدودة (FSM). يوضح الشكل الموجود على اليمين آلة الحالة المحدودة ، وهي نوع معروف من الآلات الآلية. يتكون هذا الجهاز الآلي من حالات (ممثلة في الشكل بواسطة دوائر) وانتقالات (ممثلة بالسهام). نظرًا لأن الإنسان الآلي يرى رمزًا للإدخال ، فإنه يقوم بالانتقال (أو الانتقال) إلى حالة أخرى ، وفقًا لوظيفة الانتقال الخاصة به ، والتي تأخذ الحالة السابقة ورمز الإدخال الحالي كوسائط لها.

ترتبط نظرية الأوتوماتا ارتباطًا وثيقًا بنظرية اللغة الرسمية. في هذا السياق ، يتم استخدام الأوتوماتا كتمثيلات محدودة للغات الرسمية التي قد تكون غير محدودة. غالبًا ما يتم تصنيف الأوتوماتا حسب فئة اللغات الرسمية التي يمكنهم التعرف عليها ، كما هو الحال في تسلسل تشومسكي الهرمي ، الذي يصف علاقة متداخلة بين الفئات الرئيسية من الأوتوماتا. تلعب الأوتوماتا دورًا رئيسيًا في نظرية الحساب وبناء المترجم والذكاء الاصطناعي والتحليل والتحقق الرسمي.

آلات تورنج ، التي وصفها ألان تورينج لأول مرة في تورينج 1936-197 ، هي أجهزة حسابية مجردة بسيطة تهدف إلى المساعدة في التحقيق في مدى وحدود ما يمكن حسابه. صُممت "آلات تورينغ الأوتوماتيكية" ، كما أطلق عليها عام 1936 ، خصيصًا لحساب الأعداد الحقيقية.