Theory Of Computation (Automata Theory) Flashcards
Define Language
Language is a finite set of non empty strings
Alphabet
A Finite set of symbols or characters. It serves as a building block for constructing strings in a Language
String
A String is a finite sequence of symbols from an Alphabet. Strings can be as short as Zero symbols(empty string) or arbitrary long. Eg. “Hello’, “1234”
Types of finite Automata
-
Without Output
-DFA (Deterministic finite Automata)
-NDFA or NFA (Non-Deterministic finite Automata)
-E-NFA or E-NDFA (Non Deterministic Finite Automata with E-moves) -
With Output
-Moole Machine
-Mealy Machine
Define Finite Automata
Finite Automata is an abstract computing device. It is a mathematical model of a system with **discrete inputs, Outputs, states, and sets of transitions from state to state that occurs on input symbols from an alphabet:
M = (Q, ∑, δ, q0, F)
Q: finite set of states.
∑: finite set of the input symbol.
q0: initial state.
F: final state.
δ: Transition function.**
Define Kleene Star
The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including λ.
Chomsky’s classification
- Recursive
- Context sensitive
- Context- free
- Regular grammar
Chomsky type0
Recursive
Production are Without any restrictions
Turing machine
Chomsky Type1
Generates **Context sensitive ** language
Length of RHS must be => LHS
Chomsky type2
LHS must be <= rhs
LHS contains only terminals, RHS can contain terminals and non terminals
Generates Context-free grammar
Eg:
Chomskys type3
generates Regular grammar
Non-Terminal produces Terminal T=>t
Or T=> tT
Used for finite Automata
Kleene’s Closure L*
Is the infinite set of all possible length including Ɛ
