Thoeory of Automata

Theory of Automata  Study Material 

By Rabia Shahid

Finite Automata & Difference in DFA and NDFA

DFA and NDFA Slides

Language to Finite Automaton Creation

Acceptability of string by NFA

Example 1

Acceptability of string by DFA

(Example no 1)

(Example no 2)

(Example no 3) 

(Example no 4)

(Example no 5)

NFA to DFA Conversion

(Example 1)

(Example 2)

NFA to DFA Conversion (Slides)
NFA to DFA Conversion using Epsilon Closure

Books

Introduction-to-computer-theory-by-daniel-cohen
An-Introduction-to-Formal-Languages-Automata-3rd-Edition-by-Peter-Lin

Regular Languages and Finite Automata by Tripos Marcelo Fiore- Cambridge University

Online Material

Theory of Automata (Virtual University) (Video Lectures)

Theory of Automata (Tutorial Point) (Video Lectures)
Theory of Automata (Java T Point) (Video Lectures)
Online Blog

Online Notes

Theory of Automata notes Univerisity of San Francisco

Online notes

Introduction to Automata and Complexity Theory, at Stanford University.
Theory of Automata (Tutorial Point Notes)
Theory of Automata (Virtual University Notes)


*************************************************************************

Additional Links

Finite State Models: Language definitions preliminaries,

https://www.scribd.com/presentation/289945581/Theory-of-Automata
https://en.wikipedia.org/wiki/Automata_theory
https://www.tutorialspoint.com/automata_theory/automata_theory_introduction.
htm

Regular expressions/Regular languages,

https://www.sanfoundry.com/automata-theory-regular-expressions-languages/
https://www.tutorialspoint.com/automata_theory/regular_expressions.htm
https://www.sanfoundry.com/automata-theory-questions-answers-regularexpression-introduction/
https://www.cl.cam.ac.uk/teaching/1011/RLFA/LectureNotes.pdf

Finite automata (FAs),

https://www.geeksforgeeks.org/toc-finite-automata-introduction/
https://www.tutorialspoint.com/automata_theory/index.htm

Transition graphs (TGs),

https://www.docsity.com/en/transition-graph-theory-of-automata-lectureslides/203697/
http://www.zeepedia.com/read.php?
generalized_transition_graphs_theory_of_automata&b=19&c=9
https://www.sanfoundry.com/automata-theory-transition-graph-table/
https://www.coursehero.com/file/12579026/Lec04TransitionGraphs/

NFAs,

https://www.youtube.com/watch?v=f-EUv9LHi0k
https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-
045j-automata-computability-and-complexity-spring-2011/lecture-notes/

Kleene’s theorem,

http://www.zeepedia.com/read.php?
nfa_and_kleenes_theorem_theory_of_automata&b=19&c=17
http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/kleene-1.html

Transducers (automata with output),

https://www.britannica.com/topic/automata-theory/Classification-of-automata
https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-
05/automata-theory/basics.html
https://www.scribd.com/presentation/289945581/Theory-of-Automata
http://er.yuvayana.org/finite-automata-with-output-transducer-formal-definition/
https://www.tutorialspoint.com/automata_theory/automata_theory_tutorial.pdf

Pumping lemma and non-regular language

https://www.sanfoundry.com/automata-theory-questions-answers-pumpinglemma-regular-language/
https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

Grammars and PDA: CFGs,

https://www.sanfoundry.com/automata-theory-questions-answers-from-pdagrammars/
https://www.tutorialspoint.com/automata_theory/pda_context_free_grammar.ht
m
https://www.youtube.com/watch?v=uxZVcHJqLpc

Derivations, derivation trees and ambiguity,

https://www.sanfoundry.com/automata-theory-problems/
http://ce.sharif.edu/courses/93-94/2/ce415-
1/resources/root/Notes/Nazarie_Chapter%202.pdf
https://www.tutorialspoint.com/automata_theory/ambiguity_in_grammar.htm

Simplifying CFLs,

https://www.docsity.com/en/simplification-of-cfls-theory-of-automata-lectureslides/80964/
https://www.geeksforgeeks.org/theory-computation-union-intersection-regularlanguages-cfl/Normal form grammars and parsing,https://www.tutorialspoint.com/automata_theory/introduction_to_grammars.htm
https://www.sanfoundry.com/automata-theory-questions-answers-chomskynormal-form/

Decidability,

https://www.tutorialspoint.com/automata_theory/language_decidability.htm
http://www.zeepedia.com/read.php?
decidability_theory_of_automata&b=19&c=29

Context sensitive languages,

https://www.youtube.com/watch?v=mbJAPJOoVI8grammars and linear bounded automata (LBA),https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htmChomsky’s hierarchy of grammarshttps://www.geeksforgeeks.org/toc-chomsky-hierarchy/Turing Machines Theory: Turing machines,https://www.tutorialspoint.com/automata_theory/turing_machine_introduction.ht
m

Post machine,

https://www.britannica.com/art/Post-machine

Variations on TM,

https://www.scribd.com/presentation/23706790/Chapter-06-Other-AutomataModels

TM encoding,

https://cs.stackexchange.com/questions/49615/what-is-an-encoding-of-a-tm
https://www.cs.usfca.edu/~galles/cs411/lecture/lecture15.pdf

Universal Turing Machine,

https://en.wikipedia.org/wiki/Turing_machine

Defining Computers by TMs.

https://www.computerworld.com/article/2504774/data-center/how-alan-turingset-the-rules-for-computing.html
https://cs.stackexchange.com/questions/49803/defining-a-turing-machine-for-
0n-1n-01
https://cs.stackexchange.com/questions/125/how-to-define-quantum-turingmachines
https://www.cio.com/article/2394737/developer/how-alan-turing-set-the-rulesfor-computing.html