grammar
#define grammar: \
I---------------------------------------------------------------------------------------------\
I---------------------------------------------------------------------------------------------\
I---------------------------------------------------------------------------------------------\
I \
I /$$$$$$ \
I /$$__ $$ \
I | $$ \__/ /$$$$$$ /$$$$$$ /$$$$$$/$$$$ /$$$$$$/$$$$ /$$$$$$ /$$$$$$ \
I | $$ /$$$$ /$$__ $$|____ $$| $$_ $$_ $$| $$_ $$_ $$ |____ $$ /$$__ $$ \
I | $$|_ $$| $$ \__/ /$$$$$$$| $$ \ $$ \ $$| $$ \ $$ \ $$ /$$$$$$$| $$ \__/ \
I | $$ \ $$| $$ /$$__ $$| $$ | $$ | $$| $$ | $$ | $$ /$$__ $$| $$ \
I | $$$$$$/| $$ | $$$$$$$| $$ | $$ | $$| $$ | $$ | $$| $$$$$$$| $$ \
I \______/ |__/ \_______/|__/ |__/ |__/|__/ |__/ |__/ \_______/|__/ \
I---------------------------------------------------------------------------------------------\
I---------------------------------------------------------------------------------------------\
I---------------------------------------------------------------------------------------------I
• highly useful for defining computer languages { configuration; programming }
• parser generators -such as Bison- require you to write grammars
close to the formal notation
• better pieces of documentation { IBM, Microsoft (sometimes) } will include
formal grammar notation
• all grammar notations in use are dialects of the Backus-Naur Form or BNF for short
• BELOW I use a dialect that quotes, and escapes non-terminals to help readability
○ formal notation
a, b, c... : terminal symbol
A, B, C... : non-terminal symbol
...X, Y, Z : symbol
...x, y, z : string of terminal symbols
α, β, γ... : string of non-terminal symbols
Symbol: Symbol:
• primitive definition
• an atomic part of text
'a'
'b'
"asd" // NOTE: how "asd" is a single symbol, not a string of 3;
// there's nothing stopping one from defining a symbol
// to be composed of an arbitrary number of chars
• formally represented by letters from the end of the English alphabet
— terminality:
• symbols, which are place holders of an arbitrary int of any other symbols,
following an arbitrary int of schematics are called non-terminanal symbols
• every symbol which is not a non-terminal symbol is called a terminal symbol
• terminal symbols are formally represented by lower case letters
• non-terminal symbols are formally represented by upper case letters
• non-terminal symbols are "assigned" to a placeholder/schematic with "->" or "::=",
an arbitrary number of values may be separated by '|'s to assign them all
within the same expression
non-terminal symbols in strings will be escaped ('\\') for readability's sake
t := a # defines t to represent the terminal symbol 'a'
N -> b # defines N to be able to represent the terminal symbol 'b'
N ::= c | d # defines N to be able to represent the terminal symbol 'c' or 'd'
N -> ef # defines N to be able to represent the string of terminal symbols "ef";
N ::= eNf # defines N to be able to represent any string which starts with an 'e',
# has an N in the middle and ends with an 'f'
# NOTE: how it contains a non-terminal symbol;
# in this case it so happens to itself;
# recursion is allowed
# it is important to realize that our definitions do not overwrite each other,
# our current definition of N is equivalent to:
N -> b | c | d | ef | eNf
# now the string "ecdf" could very well be represented by N
• strings of terminal symbols are formally represented by lower case letters from the end of the English alphabet
• strings of non-terminal symbols are formally represented by Greek letters
Alphabet: Alphabet:
• a finite set of symbols
• to define a grammar, we have to specify what symbols will be valid inside it,
this is what an alphabet is for
operator*:
<alphabet-1> * <alphabet-2>
• results in a set of words, which can also be interpreted
as a new alphabet where every symbol is a complex one
A := {'a', 'b'}
B := {'0', '1'}
A * b = {"a0", "a1", "b0", "b1"}
operator^
<alphabet>^${n}
<alphabet>^0 = ε
• where ${n} ∈ N, <alphabet>^${n} is the ${n} times multiplication of <alphabet> with itself
A := {'0', '1'}
A ^ 2 = {"00", "01", "10", "11"}
Word: Word:
• any expression, made up from the symbols of an alphabet is called a word
• the lenght of a word is the number of symbols its made of
• _ε_ is an empty word; it is present in all languages and can be made in any alphabet
operator+:
<word-1> + <word-2> == <word-1><word-2>
• "concatenation"
• associative
• not commutative
"a" + "b" == "ab"
operator^:
<word> ^ ${n}
<word>^0 = ε
• where ${n} ∈ N, <word>^${n} is the ${n} times concatenation of itself
a := "alpha"
a^3 == "alphaalphaalpha"
operator^T:
• reverses a word
• if <word> == <word>^T then the word is called a palidrom word { "radar"; "görög" }
a := "example"
a^T == "elpmaxe"
• a word is primitive if it cannot be represented as the power of another word
a := "a" # a is primitive
b := "123123123" # b is not, as it can be expressed as "123"^3
Sets:
• sets of words that is, of course
operator⊗:
<word-set-1> ⊗ <word-set-2>
• the set of all words resulting from concatenation of
all word in operand 2 to all words in operand 1
s1 := {"Bird", "Kenguru"}
s2 := {"House", "Food"}
s1 ⊗ s2 == {"BirdHouse", "BirdFood", "KenguruHouse", "KenguruFood"}
operator^:
<word-set> ^ ${n}
<word-set>^0 = ε
• equivalent to <set> ⊗ <set>^(<signed>-1) (where '^' recursively expands until 0)
s := {"myFirstWord", "mySecondWord"}
s^1 = {
"myFirstWordmyFirstWord",
"myFirstWordmySecondWord",
"mySecondWordmyFirstWord",
"mySecondWordmySecondWord",
}
s^2 = {
"myFirstWordmyFirstWordmyFirstWord",
"myFirstWordmyFirstWordmySecondWord",
"myFirstWordmySecondWordmyFirstWord",
"myFirstWordmySecondWordmySecondWord",
"mySecondWordmyFirstWordmyFirstWord",
"mySecondWordmyFirstWordmySecondWord",
"mySecondWordmySecondWordmyFirstWord",
"mySecondWordmySecondWordmySecondWord",
}
Sentence: Sentence:
• a word with no non-terminal symbols in it
Language: Language:
• a set of sentences
• usually defined by rules which generate sentences which are part of the language,
rather than list-ing all elements
• a language is called finite if it has a finite number of elements
• a language is called infinit if it has an infinite number of elements
Sigma: Sigma:
Σ
• the set of terminal symbols of an alphabet, ie. all 1 long words of an alphabet
• a formal language is a subset of the Σ* of an alphabet
Generative: Generative:
• defined as a 4-tuple of a set of non-terminals (N),
a set of terminals (Σ), a set of rules (P) and a start symbol (S)
G(N, Σ, P, S)
N := non-terminal symbols
Σ := terminal symbols
S := start symbol
S ∈ N # formality
P ⊆ (N U Σ)*${n}(N U Σ)*
• any grammar that uses non-terminal symbols
Ambiguity: Ambiguity:
• a grammar is ambiguous if there's more than one left- or rightmost derivatives
that can generate the same string;
one of the conditions being true implies the other being also true
• for any word that implies the ambiguity there are more than 1 parse trees which yield it
• when creating a computer language, for obvious reasons,
you really really dont want your grammar to be ambiguous
Dangling_else:
https://en.wikipedia.org/wiki/Dangling_else
• famous example of a problematic parsing ambiguity
• relevant for Context Free Grammars (see BELOW)
• ALGOL 60 legitimately had this defect
# assume that in our programming language wishes to allow
# the following types of statements
if <...> then <...>
if <...> then <...> else <...>
# now assume the following statement
if a == 0 then
if b == 2 then
call do_something
else
call do_other_thing
# what has to be done seems obvious,
# until i change the indentation, that is
if a == 0 then
call do_something
if b == 2 then
call do_something
else
call do_other_thing
• the problem is easily solved by introducing some kind of terminator
{ sh's "fi"; C's "{}"-s }
Recursiveness: Recursiveness:
<non-terminal_symbol> ->+ (<string-1>)<non-terminal_symbol>(<string-2>)
# formally
I ->+ "X\IY"
• a grammar is recursive if it has a rule which assigns a non-terminal symbol
to a string which contains the same non-terminal symbol
• its left recursive if I ->+ "\IX"
• its right recursive if I ->+ "X\I"
Chomskys_grammar_classes: Chomskys_grammar_classes:
• any algorithm capable of solving a problem in one of Chomsky's grammar class-es in theory
should be able to solve the same problem in another grammar belonging to the same class
(with changed parameters of course)
— class-3 ⊆ class-2 ⊆ class-1 ⊆ class-0:
+---------------------------------------------------------+
| Type 0; "Unrestricted grammar" |
| |
| +-----------------------------------------------+ |
| | Type 1; "Context Sensitive grammar" | |
| | | |
| | +-------------------------------------+ | |
| | | Type 2; "Context Free grammar" | | |
| | | | | |
| | | +---------------------------+ | | |
| | | | Type 3; "Regular grammar" | | | |
| | | +---------------------------+ | | |
| | | | | |
| | +-------------------------------------+ | |
| | | |
| +-----------------------------------------------+ |
| |
+---------------------------------------------------------+
• the higher the number of Chomsky's class the less complex and permissive it gets
3:
• "regular"
• used for regular expressions (regex);
which are the common solution for matching a string to a pattern
{ collecting all emails from a website; validating a user provided phone number }
— right
# formally
A -> "a"
A -> "\Ba"
○ every rule follows
<non-terminal_symbol> -> <terminal_symbol>
<non-terminal_symbol-1> -> <non-terminal_symbol-2><terminal_symbol>
— left
# formally
A -> "a"
A -> "a\B"
○ every rule follows
<non-terminal_symbol> -> <terminal_symbol>
<non-terminal_symbol-1> -> <terminal_symbol><non-terminal_symbol-2>
# this left regular grammar generates unsigned ints (in base 10)
V := {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
W := {S}
P := {S -> "0\S", S -> "1\S", S -> "2\S", S -> "3\S",
S -> "4\S", S -> "5\S", S -> "6\S",
S -> "7\S", S -> "8\S", S -> "9\S"}
2:
• "context free"
• used for describing the syntax of programming languages
• the way "<>" expressions are notated in this very document,
follows a Chomsky's type 2 grammar
○ every rule follows
# formally
A -> ω
<non-terminal_symbol> -> <symbol>+
• the starting symbol must be allowed to be empty (S -> ε)
# this grammar generates binary numbers whose (length % 2) == 0
# NOTE: it does obviously not generate all such binary numbers, that's not our goal
N := {'0', '1'}
Σ := {S}
P := {S -> "0\S0", S -> "1\S1", S -> ε}
1:
https://en.wikipedia.org/wiki/Lexer_hack
• "context sensitive"
• used for describing the syntax of handicapable programming languages
○ every rule follows
# formally
αAβ -> αωβ
<terminal_symbol-1><non-terminal_symbol><terminal_symbol-2> -> <terminal_symbol-1>(<symbol>+)<terminal_symbol-2>
• in every rule, every non-terminal symbol has to be preserved, along with their relative position
0:
• "phase structured"
○ every rule follows
# formally
αAβ -> γ
<terminal_symbol><non-terminal_symbol><terminal_symbol> -> <symbol>+
• the only constraint is that the left side of every rule contain atleast one non-terminal symbol
• the right hand side is free to be ε
— normal form:
○ when ever rule follows
# formally
A -> BC
A -> a
<non-terminal_symbol-1> -> <non-terminal_symbol-2><non-terminal_symbol-3> or
<non-terminal_symbol-1> -> <terminal_symbol>*
• every class 2 grammar has an equivalent grammar which is in normal form
Extended_Bachus_Noir_form:
• grammar describing grammar
<non-terminal> ::= <string> : assignment operator for non-terminal symbols
. : end of rule
... : arbitrary number of repetitions of preceding symbol
[...] : 1 or more repetitions of receding symbol is required
(<...>) : grouping; how "<...>" is part of this document's builtin syntax
<string> | <string> : alternative values for the string that gets derived
"<...>" : string of terminal symbols; how "<...>" is part of *this document's builtin syntax
PARSING: PARSING:
info bison # 5 The Bison Parser Algorithm
• every valid word has atleast 1 corresponding parse tree
• algorithmically generating a word in a context free language
• visually representable in an easy to read manner
• usually implemented using a stack of tokens
N := {" - ", " + ", [0-9]} # [0-9] being the digits from 0 to 9
Σ := {S, O}
P := {S -> [0-9], S -> "\S\O\S", O -> " - ", O -> " + ", S -> ε}
# we would like to produce the sentence "1 - 4 + 2"
S
|
SOS
/|\
/ | \
/ + 2
SOS
/|\
/ | \
1 - 4
• see more AT "/C\/C++/3th party libraries/Flex\/Bison"
AUTOMATON: AUTOMATON:
• "state-automaton"
• singular: "automaton" -- plural: "automata"
• the automaton represents the theoretical background required for all computation
• a machine which performs a series of predefined steps
• most notable in the context of analysing of strings of text to
check whether they belong to a specific language;
such operation is necessary for the translation of computer languages (to machine code);
from now on "automaton" is used as a shorthand for "grammar analyzing automaton"
• every automaton takes a string as its input
• every automaton has a reading head which is capable of reading
a single symbol at the time and moving the to the next symbol
in the input string(, but not (necessarily) to the previous one)
• every automaton has the capability to store an inner state
• the automaton finishes execution when there are
no more symbols left to read from the input string;
the state in which it is at that point is what signals whether the input string valid
— for the creation of an automaton the following must be established:
• Σ
• Q; the set of possible inner states of the automaton
— function δ(state, symbol)
δ := {([state-1], [symbol], [state-2])*} : formally defines δ; means that if the automaton is in [state-1] when [symbol]
is read, then it will set its inner state to [state-2];
this part (between the parentheses) is called a rule
• the defining set is often displayed in table form
• this is a read-only automaton's δ()
Σ := {'0', '1'}
Q := {q0, q1, q2}
δ := {(q0, '0', q2), (q0, '1', q1), (q1, '1', q0), (q1, '0', q2)}
+---+----+---+----+
| δ | K | V | K |
+---+----+---+----+
| ¤ | q0 | 0 | q2 |
| ¤ | q0 | 1 | q1 |
| ¤ | q1 | 0 | q2 |
| ¤ | q1 | 1 | q0 |
+---+----+---+----+
• Qˇ0 is the initial (starting) state of the automaton (Qˇ0 ∈ Q)
• an accepting state ("elfogadó állapot"^HU) is a state which signals that the input string is valid,
if the automaton has that inner state at the end of its execution
• Qˇv is the set of accepting states of the automaton (Qˇv ⊆ Q)
• every automaton has a accepted language which is composed from the words which leave the automaton in an accepting state
• any 2 automata is equivalent if they have the same accepted language
• an automaton is called a mininal automaton if it has the least number of possible inner states for its accepted language
— completeness:
• an automaton is called complete if it has a rule for every symbol in all states
• an automaton is called partal ("parciális"^HU) if it is not complete
• if an automaton is partial it might have abruptly stop as it was
given no instructions on how to handle a situation
— determinableness:
• an automaton is not deterministic if there are multiple rules with the same starting state and symbol,
but they yield differing states { (q3, 's', q2), (q3, 's', q6) }; otherwise it is
• when a non-deterministic automaton encounters a situation when the next step is can be executed in
multiple allowed ways, it must choose
• if there exists a series of choices which end in the automaton accepting the input string,
the input string is valid
— configuration:
• what is needed for saving and later restoring an automaton
• in every case the configuration contains the remainder of the input string and the inner state
• if an automaton has 'N' number of inner states and its accepted language has a sentence which is long-er than 'N',
the language is infinite
— finite automata:
— has only all the mandatory components
• input string
• input head
• inner state
• delta function
• can only analyze regular languages
— stack automata
https://github.com/agvxov/stack_automaton
• has not only all the mandatory components (see ABOVE), but also a stack,
on which it can freely (as in restricted only by the rules of a stack)
perform I/O operations
• can analyze context free languages
— the delta function now requites an extra parameter,
the symbol stored on the top of the stack:
function δ(state, input-symbol, stack-symbol)
• for its configuration the stack must also be saved
• may not have Qˇv (set of accepting states), rather it signals the recognition of
a sentence by having an empty stack when the entirety of the input string was read
Turing_machines: Turing_machines:
https://turingmachinesimulator.com/
• named after Alen Mathison Turing, from whom no one would have ever heard of
only if Konrad Zuse would have not been "an evil Nazi"
○ has all the mandatory components of an automaton, plus
— input string:
• extended on one or both ends to infinity, so the machine
may store any information its necessary
• I/O head, which can operating on the input string at any position
• inner state ("state register")
— delta function:
— can arbitrary modify the heads position by the combination of the following instructions:
< - move left
• - move right
— - stay in place
• can analyze phase structured languages
• a mathematical model of modern computers
(but obviously, real computers dont and couldnt have infinite memory)
• there are many other models, however a Turing machine can simulate all of them
• the Church-Turing thesis is the idea that every computation device
can be simulated by a Turing Machine {silicon based; DNA based; neuron based}
• Turing machines can be represented as strings,
meaning they could serve as input to other Turing machines
{
┏━━━━━━━━━━━━━━━┓
┃ Central Unit ┃
┃ State: ┃
┃ (my_state) ┃
┗━━━━━━━┰━━━━━━━┛
│
┌─────┘
│
V
+---+---+---+---+---+---+---+---+---+---+---+
| S | 0 | 1 | 1 | 0 | 1 | 0 | 0̶ | 0̶ | 0̶ | 0̶ | ...
+---+---+---+---+---+---+---+---+---+---+---+
...
δ(…, …) := (…, …, …) δ(…, …) := (…, …, …)
δ(…, …) := (…, …, …) δ(…, …) := (…, …, …)
δ(…, …) := (…, …, …) δ(…, …) := (…, …, …)
}
{
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ q0 ┃
┗━━━━━━━┰━━━━━━━┛
│
┌─────┘
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >) <
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
┌─┘
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >) <
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ o ┃
┗━━━━━━━┰━━━━━━━┛
│
└─┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >) <
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ o ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >) <
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >) <
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >) <
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ o ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────────────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >) <
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────────────────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >) <
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────────────────────┐
│
V
+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >) <
δ(e, _) := (n, _, -)
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
┏━━━━━━━━━━━━━━━┓
┃ TM ┃
┃ e ┃
┗━━━━━━━┰━━━━━━━┛
│
└─────────────────────────────┐
│
V
+---+---+---+---+---+---+---+---+---+---+
| s | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | _ |
+---+---+---+---+---+---+---+---+---+---+
δ(e, 0) := (o, 0, >)
δ(e, 1) := (e, 1, >)
δ(e, _) := (n, _, -) <
δ(o, 0) := (e, 0, >)
δ(o, 1) := (o, 1, >)
δ(o, _) := (n, _, -)
δ(q0, s) := (e, s, >)
• accepted
}
multitape: multitape:
○ classical role of tapes
first - input
last - output; starts empty; unless there are only 2 tapes, in which case the second is memory
others - memory; starts empty
• these construction might come up while simulating a multi tape Turing Machine,
but are irrelevant in the broader context
• with the number of tapes, the complexity of δ must increase too
• can very well be faster, than single tape Turing Machines
{
┏━━━━━━━━━━━━━━━┓
┃ Central Unit ┃
┌───┃ State: ┃
│ ┃ (my_state) ┃
│ ┗━━━━━━━┰━━━━━━━┛
│ │
│ ┌─────┘
│ │
│ V
│ +---+---+---+---+---+---+---+---+---+---+---+
│ | S | 0 | 1 | 1 | 0 | 1 | 0 | 0̶ | 0̶ | 0̶ | 0̶ | ...
│ +---+---+---+---+---+---+---+---+---+---+---+
│
└─────┐
│
V
+---+---+---+---+---+---+---+---+---+---+---+
| S | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | 0̶ | ...
+---+---+---+---+---+---+---+---+---+---+---+
δ(…, …, …, …) := (…, …, …, …) δ(…, …, …, …) := (…, …, …, …)
δ(…, …, …, …) := (…, …, …, …) δ(…, …, …, …) := (…, …, …, …)
δ(…, …, …, …) := (…, …, …, …) δ(…, …, …, …) := (…, …, …, …)
}
Conversation_to_single_tape:
O(t(x)) -> DTIME(t²(x))
f(x) -> c*f(x)
• every multi tape turing machine can simulated with a single tape machine;
its computationally not all that expensive either
— tape simulation
• tapes are concatenated
• start symbols must be included
• the position of each head is virtual-ized with a special symbol;
this could be a stand alone one or a marked version for each symbol (dotted by convention)
{
V
+---+---+---+---+---+---+---+---+---+---+---+
| S | 0 | 1 | 1 | 0 | 1 | 0 | 0̶ | 0̶ | 0̶ | 0̶ | ...
+---+---+---+---+---+---+---+---+---+---+---+
V
+---+---+---+---+---+---+---+---+---+---+---+
| S | a | a | b | a | b | b | b | 0̶ | 0̶ | 0̶ | ...
+---+---+---+---+---+---+---+---+---+---+---+
V
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|:S | 0 | 1 | 1 | 0 | 1 | 0 |:S | a | a | b | a | b | b | b | ...
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
I. II.
}
• the head has to scan the full tape to simulate a single step
of its multi-taped counterpart
• whenever a new symbol is required (for storage) at the end of a tape,
all the tapes to the right are shifted away (by copying)
— cross product
• new symbols, rules and states are created
— a new symbol created for every combination
of possible symbol combination pointed at:
{
Tape 1 alphabet: {0, 1}
Tape 2 alphabet: {0, 1}
0 && 0 - a
1 && 0 - b
0 && 1 - c
1 && 1 - d
}
• new rules must be created,
requiring more states than
in the original configuration
Boolean_circut:
• model of computation
• Turing complete
• originally proposed as a "simpler" alternative to the Turing-machine
○ has the following operations
or
and
not
Modifiers: Modifiers:
non_deterministic:
• has multiple δ()s (classically 2)
• at each step, chooses arbitrary
• the input is considered accepted if there are any sequence of steps which accept it
○ either
• the 2 explanations are equivalent
• it explores all paths in parallel
• it always gets "lucky" and finds the right path at the first run
• only highly theoretical; as of now, anyways
• does not have anything to do with quantum computers
probabilistic:
• has multiple δ()s (classically 2)
• the machine has access to a true random number generator (a black box)
• multiple passes are recorded
• the input is accepted if it outputs the right answer with 2/3 probability
oracle:
• only highly theoretical; as of now, anyways
• has an "oracle" (a black box), that always provides it
with the right answer immediately
• asking the "oracle" is called quering
non_uniform:
• the machine uses different configurations to different length inputs