Automatay

shit this subject

Set Theory

Set Theory

collection of elements, used to design things like alphabets, states and language in automata

Union

Set of all elements either A or B

Intersection

•  Set of all elements common in A and B

Difference

•  Set of all elements in A but not in B or

• Set of all elements in B but not in A (depends on the diagram

Complement

 Set of all elements not in A assuming universal set

sequence and tuples

list of objects in some order

order list of elements, where the repetition is allowed

Graphs

set of objects where some pairs of objects are connected by edges

Graphs

mathematical representation of set of objec

Directed

•  with arrow one vertex to another

Undirected graph

has no arrow

Weighted graph

•   with weights

Unweighted graph

•  has no weights

Automata

• a foundation for understanding more complex computation models

Automata

Study of abstract computing devices, or “machines”

Symbols

a single from an alphabet

Alphabet

- A finite set of symbols  (crucial in automata as it determine)

String

sequence from an alphabet, denoted as Σ

Alphabet

finite, non-empty set of symbols

Alphabet

• use the symbol ∑ (sigma) to denote alphabet i.e  ∑ = {0,1}1

Strings

• a finite sequence of symbols

• Empty is string is denoted as ε (Epsilon)

ε (Epsilon)

Empty is string is denoted as

Finite Automata

Captures all possible states and transitions that a machine can take while responding to a stream

Deterministic Finite Automata (DFA)

Non Deterministic Finite Automata (NFA)

Two types of FA

Deterministic Finite Automata (DFA)

• Machine can exist one state at any given time

• For each state, transition on all possible symbols (alphabet) should be defined

Deterministic Finite Automata (DFA)

Sometimes harder due to number of states

Q

•  a finite set of states

∑

 a finite set of input symbols (alphabet)

q0

•  a start state

δ

a transition function, which is a mapping between Q x ∑ -> Q

NFA (Non-deterministic Finite Automata)

• Can exist multiple states at the same time

• Not all symbol transitions need to be defined explicitly

• General easier to construct than DFA

•  Q x ∑ -> 2^Q

a transition function of NFA

Micron’s Automata Processor

• Introduced in 2013

• 2D array of MISD (multiple instruction single data) fabric w/ thousands to millions of processing

• 1 input symbol = fed to all states

Equivalence of DFA and NFA

• A language L is accepted by DFA if and only if accepted by NFA

Transition with ε-NFA

• transition from one state to another state without consuming any additional input symbol

• Much easier to construct NFA

• ε is added on column on transition table

 ε -close

• Set of all states including itself  that can be reached from q by making numerous amount of transition

Language Recognition

• explores how to design and implement computational models, like automata, that can determine whether a given string belongs to a specific language. 

•  sets of strings derived from a finite alphabet. Grammars provide a mechanism to enumerate the sentences of a language

Regular Expressions

• a declarative way to express the pattern of any string

• More program syntax-like

• Commonly associated with use of regex in Unix Environment (i.e grep, vi, shell, perl)

• Lexical analyzer (flex or lex)

Atomic Expressions

Individual characters (like 'a', 'b', '0', '1'), the empty string (ε), and the symbol for the empty language (∅).

Union

L U M = all strings that are either in L or M

Concatenation

all strings that are of the form xy

Star(*)

Includes all strings formed by concatenating zero or more string

Mealy Machine

• output depends on the present state as well as the present input.

•  fewer states than Moore Machine.

Moore Machine

• outputs depend on only the present state.

• more states than Mealy Machine

Theory of Computation

is a branch of computer science and mathematics that focuses on understanding the fundamental capabilities and limitations of computers.

Theory of Computation

provides what problems can solve using algorithms and how efficiently they can be solved.

Computability Theory

Which can and cannot be solved by computer.

Complexity Theory

It investigates the amount of resources such as time and memory.

P

Can be solve quickly

NP

(can be verified but enough time is needed to solved) problems.

Complexity Theory

is required to solve problems using computer.

Decidable

(can be solved using algorithm).

Undecidable

(can’t be solve of any algorithm)

Decidable

Undecidable

Main goals of TOC

Type 3 - Regular Grammar Finite automata

Rules are straightforward and don’t required a lot of memory to process.

Type - 2 Context Free Grammar Push Down Automata

More complex and it describes the language with more complicated structure,

Type 1 - Context Sensitive Grammar Lenear Bound automata

Rules can be change based on what’s around the symbol and making the language more flexible and complex.

Type 0 – Recursively Enumerable Language Turing Machines

Most powerful level of hierarchy.

- It describes as any language that a computer can generate or recognize.

- Turing Machines, likely to function in computers that can use unlimited memory and solve any problem that is theoretically computable.

String

a finite sequence of symbols from an alphabet

Noam Chomsky

highly influential American linguist, philosopher, cognitive scientist, historian, social critic, and political activist.

CHOMSKY HIERARCHY

Noam Chomsky introduced ________ in 1950s is for the classification of formal Grammars.

SEQUENCE

a list of objects in some order

Boolean Logic

a mathematical system built around the two values TRUE or FALSE