📕 Automata & Formal Langugae
Automaton (plural, automata)
Automata theory provides a simple, elegant view of the complex machine that we call a computer which do computation. An automata is a construct that possess all the imdispensable features of a digital computer. It accepts input, produces output, may have some temporary storage, and can make decisions in transforming the input into the output. Formal language
A formal language is an abstraction of the general characteristic of programming languages. It consists of a set of symbols and some rules of formation by which these symbols can be combined into entities called sentence. A formal language is the set of all sentences permitted by the rules of formation. 📙 Computer Model
Simple view of computer
CPU : Central Processing Unit where the computation is done Memory : Stores data required for the computation or program itself Memory
Memory is divided into 4 different units
temporary memory - intermediate data input memory - input data ouput memory - ouput data program memory - program itself (program is executed by CPU) Computer Model
① CPU reads program
② CPU takes input data from input memory
③ Computation / During computation, use temprorary memory
④ Generated output will be transfered into output memory
💡 Example ) f(x) = x³
仮定x=2
① CPU reads the first line of instruction.
② Take x = 2 from input memory.
③ Computation → z = 4 (intermediate data)
④ z = 4 is stored in temporary memory.
⑤ CPU reads the second line of instruction.
⑥ Take z = 4 from temporary memory/Take x = 2 from input memory
⑦ Computation → y = 8 (output data)
⑧ Transfer output to output memory.
CPU can actually perfrom only one instrction at each step. 📒 Different kinds of Automata
: Automata is distinguished by the temporary memory
Finite Automata : NO temporary memory Pushdown Automata : STACK (use temporary memory as stack) Turing Machine : RANDOM ACCESS MEMORY 1. Finte Automata
Small computing power Ex) Vending Machine Regular expression 2. Pushdown Automata
Medium compution power Ex) Compilers for progarmming languages Context-free文法(コンテキストフリー構文)3. Turing Machine
Highest computing power Modern Computer 💡 Power of Automata
: Range of computational problems that automata can solve
Finte Automata < Pushdown Automata < Turing Machine
📗 Why Study Automata Theory?
1. Finite Automata & Regular Expression
Finete Automata models protocols, electronic circuits, etc. ⭐⭐ Equivalance Check : Finte Automata (Software) models Hardware. Hardware somehow can go failure(output + noise). But software still produce output. So it can validate hardware (test whether hardware work correctly or nor) Regular expression are used in many systems
ex) in Linux OS : *.txt (all files with .txt)
XML XML (eXtensible Markup Language)
ウェブページを生成するHTMLを大幅に改良することによって生成される言語.Webページの構築機能、検索機能などが向上し、Webページの追加や作成が容易になりました.
file format called XML this kind of files can easily part using finite automation は、構造化された文書を送信することができる
HTMLでは、CPU 2.83 GHzのデータタグにおいて、どこからどこまでが実際のデータであるかを表示する適切な方法はない.ただし、XMLは、データ名、実データ、データ単位をマークすることができる.すなわち、データの意味を付与するメタデータを記述することができる. <dataname>CPU</dataname>
<datavalue>2.83</datavalue>
2. Pushdown Automata & Context-free Grammars
Every modern compiler uses pushdown automata concepts. Context-free grammars are used to describe the syntax of essentially every modern programming language. 文脈無関係文法（CFG）
CFGは、汎用言語内のすべての可能な文字列パターンを生成するための形式構文(フォーマット構文)である.
3. Turing Machine
Automata is essential for the study of the limits of computation. Undeciable : no program can solve the problem. Intractable : there are programs can solve the problem, but no fast program.