Video chapters • Chapter-1 (Basic Concepts and Automata Theory):

• Chapter-1 (Basic Concepts and Automata Theory): Introduction to Theory of Computation- Automata, Computability and
Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Introduction to Theory of Computation- Automata,
Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-
Transition, Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore Machine, Mealy Computability and Complexity, Alphabet, Symbol, String,
Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata.
• Chapter-2 (Regular Expressions and Languages): Regular Expressions, Transition Graph, Kleen’s Theorem, Finite Automata Formal Languages, Deterministic Finite Automaton (DFA)-
and Regular Expression- Arden’s theorem, Algebraic Method Using Arden’s Theorem, Regular and Non-Regular Languages-
Closure properties of Regular Languages, Pigeonhole Principle, Pumping Lemma, Application of Pumping Lemma, Definition, Representation, Acceptability of a String and
Decidability- Decision properties, Finite Automata and Regular Languages
• Chapter-3 (Regular and Non-Regular Grammars): Context Free Grammar(CFG)-Definition, Derivations, Languages, Derivation Language, Non Deterministic Finite Automaton (NFA),
Trees and Ambiguity, Regular Grammars-Right Linear and Left Linear grammars, Conversion of FA into CFG and Regular
grammar into FA, Simplification of CFG, Normal Forms- Chomsky Normal Form(CNF), Greibach Normal Form (GNF), Chomsky Equivalence of DFA and NFA, NFA with ε-Transition,
Hierarchy, Programming problems based on the properties of CFGs.
• Chapter-4 (Push Down Automata and Properties of Context Free Languages): Nondeterministic Pushdown Automata Equivalence of NFA’s with and without ε-Transition, Finite
(NPDA)- Definition, Moves, A Language Accepted by NPDA, Deterministic Pushdown Automata(DPDA) and Deterministic
Context free Languages(DCFL), Pushdown Automata for Context Free Languages, Context Free grammars for Pushdown Automata with output- Moore Machine, Mealy Machine,
Automata, Two stack Pushdown Automata, Pumping Lemma for CFL, Closure properties of CFL, Decision Problems of CFL,
Programming problems based on the properties of CFLs. Equivalence of Moore and Mealy Machine, Minimization of
• Chapter-5 (Turing Machines and Recursive Function Theory): Basic Turing Machine Model, Representation of Turing
Machines, Language Acceptability of Turing Machines, Techniques for Turing Machine Construction, Modifications of Turing Finite Automata.
Machine, Turing Machine as Computer of Integer Functions, Universal Turing machine, Linear Bounded Automata, Church’s
http://www.knowledgegate.in/gate
Thesis, Recursive and Recursively Enumerable language, Halting Problem, Post’s Correspondance Problem, Introduction to
Recursive Function Theory. http://www.knowledgegate.in/gate

INTRODUCTION TO THEORY OF • As word suggests ‘TOC’ is the study of 'mathematical' machines or systems
COMPUTATIONS called automata.
• Theory of computation can be considered as the study of all kinds of
• The theory of computation is a branch of computational model in the field of computer science and it also considers how
theoretical computer science that deals with efficiently the problem can be solved (but not is depth).
the study of algorithms and computational
complexity. It aims to answer fundamental
questions about
• what can be computed
• how efficiently it can be done
• and what limitations exist in terms of
computational power.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
PROBLEM SOLUTION
• Now a day’s machines (digital, analog, mechanical) play a very • We need a language for communication with machines. But we do not require
important role in the development of human, we need some natural languages to communicate with the machines, as natural languages are
very complex and machine interaction require very fewer complex languages
mechanism (language) to communicate with the machines. compare to natural languages.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Languages can be of two types formal languages and informal languages, here in METHODS TO DEFINE LANGUAGE
this subject we will only discuss formal languages. • In natural language we define the list of words in a dictionary because they are
finite and predefined, but we cannot list all the sentence which can be formed
• Dictionary defines the term informally as ‘a system suitable for the expression of
certain ideas, facts or concepts including a set of symbols for their manipulation’. using these words as they are infinite.

• So, we have a mechanism called grammar/rules

using which we can decide which sentence is valid
and which is invalid.
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
MATHEMATICL DEFINATION OF LANGUAGE • ALPHABET- An alphabet is a finite non empty set of symbols,
(every language has its own alphabet). here in toc, we use symbol
• SYMBOL- Symbols are the basic building blocks, which Σ for depicting alphabet. e.g. Σ = {0,1}. for English Σ = {a, b, c, …., z}
can be any character/token. (cow, sheep, , white flag, (in English also alphabet is a set of letters, thought in general we
, , etc.) (in English we called them as letters). called them as alphabet).

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• STRING - It is a finite sequence of symbols (which are the • LANGUAGE - A language is defined as a set of strings. (in natural
member of set alphabet). E.g. Σ = {a, b} String- aabb, aa, b, so language (set of words(predefined) and grammar) we apply this
on. (in English we called them as words). model from words to sentence).
• In the next level we consider programs as a string and programming
constructs/tokens like int, floats as letters/symbols.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Similarly, in our system we have finite number of symbols/letters but using those
letters we can generate infinite strings/words. Machine Grammar
• So, we may have languages that have infinite number of words, so it is not
possible for us to list them, we have to use some framework, which can
somehow represent the same language. There are mainly two methods to
represent a language
• by a grammar that generates a language [RG generate RL]
• by a machine that accepts a language [FA accept RL language]

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• The Theory of Formal Languages is a branch of theoretical computer science that

deals with the study of formal languages and their properties. Q if ∑ = {a, b} then, find the following?
• The theory of formal languages includes the study of formal grammars, which are
used to define the syntax of formal languages, and automata theory, which deals ∑0 =
with the study of abstract machines used to recognize, generate, or process
formal languages. Some of the key concepts studied in the theory of formal
languages include regular languages, context-free languages, context-sensitive ∑1 =
languages, recursively enumerable languages, and the Chomsky hierarchy.
• The theory of formal languages has important applications in areas such as ∑2 =
compilers, parsers, and other software engineering tools, as well as in the design
of programming languages and the study of natural language processing.
∑3 =

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• ∑K is the set of all the strings from the alphabet ∑ of length exactly K. Kleene closure- If ∑ is a set of symbols, then we use ∑* to denote the set of
strings obtained by concatenating zero or more symbols from ∑ of any length,
in general any string of any length which can have only symbols specified in ∑.
• ∑k = {W | |W| = K} (using the symbols from the alphabet ∑)

• ∑* = ⋃!"$
!"# 𝑤 𝑤 = 𝑖} (using the symbols from the alphabet ∑)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Positive closure – If ∑ is a set of symbols, then we use ∑+ to denote the set of Automaton
strings obtained by concatenating one or more symbols from ∑ of any length, • An automaton is defined as a self-operating system where energy, materials and
in general any string of any length which can have only symbols specified in ∑ information are transformed, transmitted and used for performing some functions
without direct participation of man.
(except ∈).
• The term is often used to describe a theoretical machine that operates according to a
set of rules and is capable of carrying out complex operations without human
• ∑+ = ⋃!"$
!"% 𝑤 𝑤 = 𝑖} (using the symbols from the alphabet ∑) intervention.
• Example: automatic machine tools, automatic packing machines, and automatic photo
printing machines.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
FINITE AUTOMATA • Finite automata can be broadly classified into two types-
• A Finite automaton is a model that has a finite set of states (represented in the figure by
circles) and its control moves from one state to another state in response to external inputs 1. Finite automata without output
(represented by arrows).
1. Deterministic finite automata.
• It is an abstract machine that is used to recognize patterns in strings of symbols. Finite 2. Non deterministic finite automata.
automata are widely used in computer science for pattern matching, lexical analysis, and
3. Non deterministic finite automata with ∈
parsing, among other applications.

2. Finite automata with output

1. Moore machine
2. Mealy machine

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• In general, this type of automata is characterized by machine having no DETERMINISTIC FINITE AUTOMATA
temporary storage, as it is severely limited in its capacity to remember things A deterministic finite automaton (DFA) is defined by 5-tuple (Q,S,d,S,F)
during the computation.
where:
• Only finite amount of information can be in the control unit by placing the unit • Q is a finite and non-empty set of states
into a specific state but since the number of states is finite, a finite automaton • S is a finite non-empty set of finite input alphabet
can only deal with situation in which the information to be stored at any time is
• d is a transition function, ( d: Q × S à Q)
strictly bounded.
• S is initial state (always one) (SÎ Q)
• F is a set of final states (F Í Q) (0<=|F|<=N, where n is the number of
states)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
DFA Designing Q Design a minimal DFA that accepts all strings over the
• A language a said to be regular language if it can be accepted by a alphabet ∑ = {a, b}, where every accepted string ‘w’ starts with
DFA. substring s = ‘abb’
• The best knowledge about DFA can be only understood by designing a
number of DFA, by doing so we will first understand the process of
DFA designing and secondly, we will understand Regular Language.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a minimal DFA that accepts all strings over the Q Design a minimal DFA that accepts all strings over the
alphabet ∑ = {a, b}. where every accepted string ‘w’ ends with alphabet ∑ = {a, b}. where every accepted string ‘w’ contains sub
substring ‘s = bab’ ? string s= ‘aba’?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• The various components of the block diagram are
explained as follows:
NOTE-
• Produces a unique computation (or run) of the automaton for each input string.
• Input tape: The input tape is divided into squares,
each square containing a single symbol from the • Deterministic refers to the uniqueness of the computation.
input alphabet ∑. The end squares of the tape
contain the end marker ¢ at the left end and the end • DFAs are useful for doing lexical analysis (Spell check) in compiler design.
marker $ at the right end. The absence of end
markers indicates that the tape is of infinite
length. The left-to-right sequence of symbols
between the two end markers is the input string to
be processed.
• Reading head (R-head): The head examines only one
square at a time and will move one square to the
right.
• Finite control: is the inference engine take care of
transition
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Representation ACCEPTANCE BY DFA

TRANSITION STATE DIAGRAM- (Graphical, easy to understand, easy
to design) A transition graph or a transition system is a finite S • Let ‘w’ be any string designed from the alphabet S, corresponding to w, if there
directed labelled graph in which each circle represents a state and d exist a transition for which it starts at the initial state and ends in any One of the
a b final states, then the string ‘w’ is said to be accepted by the finite automata. δ*
the directed edges indicate the transition of one state to another
state. The initial state is represented by a circle with an arrow q0 (q0, w) = qf for some qf ∈ F.
Q
pointing towards it, the final state by two concentric circles. q1
• Mathematically, it can be represented as: - L(M) = {w Î S* | d*(S, w) ÎF}

TRANSITION TABLE- it is a two-dimensional table where number of

columns is equal to number of input alphabets and number of rows
is equal to number of states.

TRANSITION ID- δ {qi, a) = qj, this means that on a state qi take an

input symbol a machinehttp://www.knowledgegate.in/gate
will make a transition qj http://www.knowledgegate.in/gate
Q Design a minimal DFA that accepts all strings over the Q Design a minimal DFA that accepts all strings over the
alphabet ∑ = {a, b} such that every accepted string start and end alphabet ∑ = {a, b} such that every accepted string start and end
with ‘a’? with same symbol?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a minimal DFA that accepts all strings over the Q Design a minimal DFA that accepts all strings over the
alphabet ∑ = {a, b} such that every accepted string start and end alphabet ∑ = {a, b} such that every accepted string w, is like
with different symbol? w=SX. S=aaa/bbb?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a minimal DFA that accepts all strings over the Q Design a minimal DFA that accepts all strings over the
alphabet ∑ = {a, b} such that every accepted string w, is like alphabet ∑ = {a, b} such that every accepted string w, is like
w=XS. S=aaa/bbb? w=XSX. S=aaa/bbb?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a minimal DFA that accepts all strings over the alphabet ∑ Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, b},
= {a, b}, such that every string ‘w’ accepted must be like such that every string accepted must contain exactly two a’s, |w|a=2 ?
i) |w| = 3

ii) |w|<=3

iii) |w|>=3

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a,
b}, such that every string accepted must contain at least two a’s, b}, such that every string accepted must contain at most two a’s,
|w|a >= 2 ? |w|a <= 2 ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a,
b}, such that every string ‘w’ accepted must be like b}, such that every string accepted must contain
i) |w| = 0(mod 3) ii) |w|=1(mod 4) i) number of a is, |w|a = 0(mod 2)

iii) number of a is |w|b = 2(mod 3)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a,
b} such that for every accepted string 2th from left end is always a ? b} such that for every accepted string 2nd from right end is always b ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, Q Design a minimal DFA that accepts all strings over the alphabet ∑ =
b}, such that every string accepted must contain be like, {0,1}, such that every string ‘w’ which is accepted has a decimal
no of a = 0(mod 2) || no of b = 0(mod 2) ? equivalent 0(mod 3) ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
COMPLIMENT OF DFA NON DETEMINISTIC FINITE AUTOMATA
• Non determinism means choice of move for an automaton. So rather than prescribing a
Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, unique move in each situation, we allow a set of possible moves.
b}, such that every string accepted must not contain a substring ’aaa’?
• Non deterministic machine are only theoretical machine i.e. in the first place they are not
implementable and neither we want to implement them, the only reason we study non-
determinism is because they are easy to design and easily be converted into deterministic
machine.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

FORMAL DESCRIPTION OF NDFA Some points to remember

• A Non-Deterministic finite automaton (NDFA) is a 5-tuple (Q,S,d,S,F) • Every DFA is also an NFA.
where: • Every NFA can be translated to an equivalent DFA, so their language accepting capability is
• Q is a finite and non-empty set of states same.
• NFAs like DFA’s only recognize regular languages.
• S is a finite non-empty set of finite input alphabet
• It need not to be a complete system. There can be a state that doesn’t have any transition on
• d is a transition function d: Q × S à 2Q some input symbol.
• It is possible that a single state led to multiple transition on same input to different states.
• q0 is initial state (always one) (q0Î Q)
• NOTE- A null transition is also possible for NFA, such special NFA are called Null-NFA. We will
• F is a set of final states (F Í Q) (0<=|F|<=N), where n is the number of states discuss it later.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
PROPERTIES OF NFA ACCEPTANCE BY NDFA
• Let ‘w’ be any string defined over the alphabet S, corresponding to w, there can
• i) Accepting power of NDFA= Accepting power of DFA.
be multiple transitions for NFA starting from initial state, if there exist at least
• ii) NDFA is a theoretical engine and is not implementable, but it is very easy to one transition for which we start at the initial state and ends in any One of the
design compare to DFA. final state, then the string ‘w’ is said to be accepted by the non-deterministic
finite automata, otherwise not.
• iii) No concept of dead state, therefore complementation of DFA is also not
possible. • Mathematically, it can be represented as, L(M) = {w Î S* | d*(q0, w) ÎF}
• iv) NDFA will respond for only valid strings and no need to respond for invalid
strings. (it is a Incomplete system)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a NDFA that accepts all strings over the alphabet ∑ = {a, b}, Q Design a NDFA that accepts all strings over the alphabet ∑ = {a, b}.
where every accepted string ‘w’ starts with substring s, Where s = ‘aba’ ? where every accepted string ‘w’ ends with substring ‘s’, Where s = ‘bab’?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a minimal DFA that accepts all strings over the alphabet ∑ = {a, Q Design a NDFA that accepts all strings over the alphabet ∑ = {a, b}
b}. where every accepted string ‘w’ contains sub string s, Where s = ’aba’ ? such that every accepted string start and end with same symbol ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a NDFA that accepts all strings over the alphabet ∑ = {a, b} such Q Design a minimal NDFA that accepts all strings over the alphabet ∑ =
that every accepted string start and end with different symbol ? {a, b} such that every accepted string w, is like w=SX , Where s = aaa/bbb

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a minimal NDFA that accepts all strings over the alphabet ∑ = Q Design a minimal NDFA that accepts all strings over the alphabet ∑ =
{a, b} such that every accepted string w, is like w=XS , Where s = aaa/bbb {a, b} such that every accepted string w, is like w=XSX , Where s =
aaa/bbb ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a NDFA that accepts all strings over the alphabet ∑ = {a, b} NFA and DFA Equivalence
such that for every accepted string 3rd from right end is always a ? • In this topic we will be learning about the equivalence of NFA and DFA and how
an NFA can be converted to equivalent DFA. Let us take an example and
understand the conversion.
• Since every NFA and DFA has equal power that means, for every language if a
NFA is possible, then DFA is also possible.
• So, every NFA can be converted to DFA.
• The process of conversion of an NFA into a DFA is called Subset Construction.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• If NFA have ‘n’ states which is converted into DFA which ‘m’ Procedure for Conversion
states than the relationship between n and m will be • There lies a fixed algorithm for the NFA and DFA conversion. Following things
must be considered
• 1<= m <= 2n • Initial state will always remain same.
• Start the construction of d’ with the initial state & continue for every new
state that comes under the input column and terminate the process
whenever no new state appears under the input column.

• Every subset of states that contain the final state of the NFA is a final state in
the resulting DFA.

• d’(q0 , q1, q2 , q3--------, qn-1,a) = ⋃!"$%&

!"# d( qi , a)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Aspect DFA (Deterministic Finite Automata)
NDFA (Nondeterministic Finite NFA WITH EPSILON MOVES (€-NFA)
Automata)
• An automaton that consist of null transitions is called a Null- NFA i.e. we allow a transition on
On each input symbol, transitions to Can transition to multiple states or null means empty string.
State Transition • €-NFA is a 5-tuple (Q,S,d,S,F) where:
exactly one state. none on the same input symbol.
• Q is a finite and non-empty set of states
Determinism and Each state has a unique transition for A state can have multiple transitions
Uniqueness each input symbol. for the same input symbol. • S is a finite non-empty set of finite input alphabet

Always has a single, unique • d is a transition function d: (Q × {S U ε}) à 2Q

May have multiple computation paths
Computation Path computation path for any input
for the same input string. • S is initial state (always one) (SÎ Q)
string.

Generally simpler and more Can be more complex to construct • F is a set of final states (F Í Q) (0<=|F|<=N, where n is the number of states
Ease of Construction
straightforward to construct. due to non-determinism.

Accepts an input if it reaches a final Accepts an input if at least one

Acceptance of Input state after processing all input computation path reaches a final
http://www.knowledgegate.in/gate
symbols. state. http://www.knowledgegate.in/gate

NULL-CLOSURE • Every state is at zero distance to itself.

• Null closure of a set Q is defined as a set of all the states, which are at zero distance • In NFA or DFA, distance between two states is always 1, because there
from the state Q. A set of all the states, that can be reached from the state and along a
null- transition.
could be no null transitions.
• €-Closure(qi)- The set of all the states which are at zero distance from the state qi is • The Null closure Q is always a non-empty and finite state, because
called €-closure(qi). Or the set of all the states that can be reached from the state qi every state’s null closure is that state only.
along € labelled transition path, is known as €-closure(qi).
• €-closure(Φ) = Φ
• €-closure (q0 , q1, q2 , q3--------, qn) =⋃!"$
!"# d( €-closure(qi))

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
EQUIVALENCE BETWEEN NULL NFA TO NFA
• There will be no change in the initial state.
• No change in the total no. of states
• May be change in the number of final states.
• All the states will get the status of the final state in the resulting NFA,
whose €-closure contains at least one final state in the initial €-NFA.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Let us check for ẟ(q0, a) = ε-Closure [ẟ[ε-Closure(q0), a]]

• first, we find ε-Closure of q0: {q0, q1, q2}
• Now check transition of all three states on input symbol a we get: q0
• After that we again calculate the ε-Closure of the above result q0, we get the result as: {q0, q1,
q2}
• Similarly, we will check it for every state.
• All those states will be considered as a final state in which we have q2(final state in initial ε-
NFA) in there ε-Closure, i.e. all states will be final in this case.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Moore and Mealy Machine Moore Machine
• Both moore and mealy machine are special case of DFA A Moore machine is a six-tuple (Q, ∑, Δ, δ, λ, q0), where
• Both acts like o/p producers rather than language acceptors
• In moore and mealy machine no need to define the final states • Q is a finite set of states:
• No concepts of dead states and no concepts of final states
• Mealy and Moore Machines are equivalent in power. • ∑ is the input alphabet:
• Δ is the output alphabet.
• δ is the transition function Q x ∑ into Q
• λ is the output function mapping Q into Δ and
• q0 is the initial state.

George H Mealy Edward F Moore

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Examples: The below table shows the transition table of a Moore Machine. • In moore machine for every state output is associated.

• If the length of i/p string is n, then length of o/p string will be n+1

• Moore machine response for empty string Î

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q construct a Moore machine take all the string of a’s and b’s as i/p and Q construct a Moore machine take all the string of a’s and b’s as i/p and counts
counts the no of a’s in the i/p string in terms of 1, ∑ = {a, b}, Δ = {0, 1}? the no of occurrence of sub-string ‘ab’ in terms of 1, ∑ = {a, b}, Δ = {0, 1}?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q construct a Moore machine where ∑ = {0, 1}, Δ = {a, b, c}, machine should give Mealy Machine
o/p a, if the i/p string ends with 10, b if i/p string ends with 11, c otherwise?
• Mealy machine is a six-tuple (Q, ∑, Δ, δ, λ, q0), where all the symbols except λ
have the same meaning as in the Moore machine. λ is the output function
mapping Q x ∑ into Δ.

• In case of mealy machine, the output symbol depends on the transition.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Example: The below table shows the transition table of a Mealy Machine. • If the length of i/p string is n, then length of o/p string will be n

• Mealy machine do not response for empty string Î

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q construct a Mealy machine take all the string of a’s and b’s as i/p and Q construct a Mealy machine take all the string of a’s and b’s as i/p and counts
counts the no of a’s in the i/p string in terms of 1, ∑ = {a, b}, Δ = {0, 1}? the no of occurrence of sub-string ‘ab’ in terms of 1, ∑ = {a, b}, Δ = {0, 1}?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q construct a Mealy machine where ∑ = {0, 1}, Δ = {a, b, c}, machine should give CONVERSION OF MOORE TO MEALY MACHINE
o/p a, if the i/p string ends with 10, b if i/p string ends with 11, c otherwise? • Let us take an example to understand the conversion:
• Convert the following Moore machine into its equivalent Mealy
machine.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• To convert a mealy machine to moore machine all you need to do is just push out PROCEDURE FOR TRANSFORMING A MEALY MACHINE INTO A MOORE MACHINE
the outputs of states onto to the incoming transitions. Consider the Mealy Machine:
• While conversion from moore to mealy machine, the number of states will we
same and there will be no extra states.
• The equivalent Moore Machine will be:

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Aspect Moore Machine Mealy Machine MINIMIZATION OF FINITE AUTOMATA
Produces an output • The process of elimination of states whose presence or absence doesn’t affect the
Response to Null
corresponding to the initial Does not produce any output. language accepting capability of deterministic Finite Automata is called minimization of
Input
state. automata and the result is minimal deterministic finite automata or commonly called
Output Length for Generates an output string of Generates an output string of as minimal finite automata as MFA.
Input of Length n length n+1. length n.
The initial output is • NOTE- MFA is always unique for a language.
No initial output until an input
Initial Output determined by the initial
is provided.
state.
Output Output is synchronized with the
Output is one step behind
Synchronization input; changes immediately
the input.
with Input with input.
Suitable for applications Ideal for applications requiring
Typical Use Cases where stable output is immediate response to input
http://www.knowledgegate.in/gate
necessary. changes. http://www.knowledgegate.in/gate

• It is sometimes difficult to design a minimal DFA directly so, a better approach is to first NON- PRODUCTIVE STATES- These states don’t add anything to the language
design the DFA and then minimize it. accepting power to the machine. They can further be divided into three types-
• Based on productivity, the states of DFA can be mainly classified in two types-
• Dead State
• PRODUCTIVE STATES- State is said to be productive, if it adds any accepting power to
the machine that is its presence and absence effect the language accepting capability
• Unreachable Sate
of the machine.

• NON- PRODUCTIVE STATES- These states don’t any add anything to the language • Equal State
accepting power to the machine.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Dead State- It is basically created to make the system complete, can be defined as a • Unreachable Sate- It is that state which cannot be reached starting
state from which there is no transition possible to the final state. from initial state by parsing any input string.
• In a DFA there can be more than one dead state but logically always one dead state is
sufficient to complete the functionality.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Equal State-These are those states that behave in same manner on each and Procedure of Minimization
every input string. That is for any string w where w Î S* either both of the states • For this first of all, group all the non-final states in one set and all final states in another
will go to final state or both will go to non-final state. (remember the example of set.
an equal state DFA). • Now, on both the sets, individually check, whether any of the underlying elements (states)
of that particular set are behaving in the same way, that is are they having same
• More formally, two states ql and q2 are equivalent (denoted by q1≅ q2) if both δ transition(to same set) on each input alphabet.
(q1, x) and δ (q2, x) are final states or both of them are non-final states for all x ∈ • if the answer is yes, then these two states are equal, otherwise not.
∑*. If q1 and q2 are k-equivalent for all k ≥ 0, then they are k-equivalent.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Chapter-2 (Regular Expressions and Languages): Regular Expressions
• One way of describing regular language is via the notation of regular expression. An
Regular Expressions, Transition Graph, Kleen’s expression of strings which represents regular language is called regular expression. The
Theorem, Finite Automata and Regular Expression- regular expressions are useful for representing certain sets of strings(Language) in an algebraic
fashion.
Arden’s theorem, Algebraic Method Using Arden’s • We give a formal recursive definition of regular expressions over ∑ as follows:

Theorem, Regular and Non-Regular Languages- • Any terminal symbol (i.e. an element of ∑), ∈ and Φ are regular expressions (Primitive
regular expressions).
Closure properties of Regular Languages, • A regular expression is valid iff it can be derived from a primitive regular expression by a
Pigeonhole Principle, Pumping Lemma, Application finite number of applications of operators.

of Pumping Lemma, Decidability- Decision

properties, Finite Automata and Regular Languages
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Regular Language:- Any set(language) represented by a regular Operators

expression is called a Regular language. If for example, a, b ∈ ∑, then • When we view a in ∑ as a regular expression, we denote it by a.
• R = a denotes the L = {a} • If R is a regular expression, then (R) is also a regular expression.
• The iteration (or closure) of a regular expression R written as R*, is also a
regular expression.
• R = a.b denotes L = {ab} concatenation
• The iteration (or closure) of a regular expression R written as R+, is also a
regular expression.
• R = a + b denotes L = {a, b} Union • The concatenation of two regular expressions R1 and R2, written as R1 R2, is
also a regular expression.
• R = a* denotes the set {∈, a, aa, aaa, ...} known as Kleene closure. • The union of two regular expressions R1 and R2, written as R1 + R2, is also a
regular expression.
• R = a+ Positive closure {a, aa, aaa…}

• R =(a + b)* denotes {a, b}*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Operator Precedence IDENTITIES FOR Regular Expression

• The precedence order to solve is • Two regular expressions P and Q are equivalent (we write P = Q)
• ()Bracket • if P and Q represent the same set of strings.

• * (Kleene Closure)

• + Positive Closure

• Concatenation

• Union

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Every regular expression can generate only one regular language but, a regular हमार% language बताओ
language can be generated by more than one regular expression I.e. means two
different regular expression can generate same language.

• Two regular expression are said to be equal if they generate same language. 1. R={a}
• r1 = a*

• r2 = a* + (aa)* 2. R={a + b}

3. R={a + b + c}

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
1. R={a.b} Q Design a regular expression that represent a language ‘L’, where L={a}
over the alphabet ∑={a}.

2. R={a.b + a}b

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q design a regular expression that represent all strings over the alphabet Q design a regular expression that represent all strings over the alphabet
∑ = {a, b}, where every accepted string ‘w’ starts with substring s = ‘abb’ ∑ = {a, b}. where every accepted string ‘w’ ends with substring s = ‘bab’?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑ = {a, b}. where every accepted string ‘w’ contains sub string s alphabet ∑ = {a, b} such that every accepted string start and end with a.
= ‘aba’ ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑ = {a, b} such that every accepted string start and end with alphabet ∑ = {a, b} such that every accepted string start and end with
same symbol? different symbol ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑ = {a, b} such that every accepted string w, is like w=SX S = alphabet ∑ = {a, b} such that every accepted string w, is like w=XS. S =
‘aaa/bbb’ ? ‘aaa/bbb’ ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑ = {a, b} such that every accepted string w, is like w=XSX. S = alphabet ∑ = {a, b}, such that every string ‘w’ accepted must be like
aaa/bbb ? i) |w| = 3 ii) |w|<=3 iii) |w|>=3

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑ = {a, b} such that for every accepted string 2 from left end is alphabet ∑ = {a, b} such that for every accepted string 4th from right end
nd

always b. is always a.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑= {a, b}, such that every string ‘w’ where |W| = 0(mod 3)? alphabet ∑= {a, b}, such that every string ‘w’ where |W| = 3(mod 4)?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a regular expression that represent all strings over the Q Design a regular expression that represent all strings over the
alphabet ∑= {a, b}, such that every string ‘w’ where |W|a = 0(mod 3)? alphabet ∑= {a, b}, such that every string ‘w’ where |W|b = 2(mod 3)?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Algebraic Properties of regular expression • Associative Property- Regular expression satisfy associative property with
respect to union and intersection
• Closure Property - Regular expressions satisfy closure property with respect to
Union, Concatenation and kleene closure. If R1 and R2 are regular expression
then the following will also be regular expression.
(r1 + r2) + r3 r1 + (r2 + r3)
r1 + r2

r1.r2
(r1. r2). r3 r1. (r2. r3)
r1*

r1+
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Identity Property- The identity property is satisfied as follows- • Commutative Property- Regular expressions are commutative with
respect to union but not with respect to concatenation.
r. = r
r1+ r2 r2+ r1
r+ = r
r1. r2 r2. r1

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Distributive Property-Regular expression satisfy this property as follows- • Idempotent Property-regular expressions satisfies idempotent
property with respect to union but not with respect to concatenation.
r1(r2+r3) r1r2+r1r3

r1+r1 r1
(r1+r2) r3 r1r3+r2r3

r1+(r2. r3) (r1+r2)(r1+r3) r1. r1 r1

(r1.r2) + r3 (r1 +r3). (r2 + r3)
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Conversion from Finite Automata to regular expression

Q Write regular expressions for the following machines

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Conversion from regular expression in Finite Automata iv) (R1*R2.R3*)

i) R*

v) R = a*b(ab)*
ii) (R1.R2)*

vi) R = (a + ba)*ab*
iii) (R1+R2)*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
vii) R = (aa + aaa)* 1. 0 * 10 * 10 *

2. ((ab)* + c*)*

viii) R = (a + aaaaa)*
3. (∈ + a + aa + aaa)b* + (a + b)* ba(a + b)*

4. 0*(10 * 1*)*0*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

1. a*b(b * + aa*b)* EQUIVALENCE BETWEEN Regular Expression AND FINITE AUTOMATA

• ARDEN’S THEOREM is the mechanism for the construction of a regular

expression from a finite automaton.

2. ((11*0+0)(0 + 1)*0*1*)

3. (ab+ bc+ acc).(a+ bc)*.( ∈+ bc*a)*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Consider a DFA and convert it into regular expression using Arden’s theorem? • Steps used-
d(A, a) = A • For, every individual state of the DFA, write an expression for every incoming
d(A, b) = B and outgoing input alphabet.
d(B, a) = B • Apply Arden’s theorem as follows-
d(B, b) = B • If P is free from NULL, then equation R=Q+RP has unique solution, R=QP*
A is the initial state and B Is the final state • If P contains NULL, then equation R=Q+RP has infinitely many solutions.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Consider a DFA and convert it into regular expression using Arden’s theorem? Transition Graph
d(A, b) = A
d(A, b) = B • Same as Î-nfa Can have more than one initial state .
d(B, a) = C • Non-Deterministic in nature (so no dead state is required, can take
d(C, b) = C multiple moves).
A is the initial state and B,C Is the final state • Can have string as a input to transition from one state to another.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Kleene’s Theorem Closure Properties of Regular Languages
• The theorem has two main parts: • Regular languages are closed under following operations
• Kleen Closure
• For any given regular expression, there is an equivalent finite automaton
(either deterministic or non-deterministic) that recognizes the same • Positive closure
language. • Complement
• For any finite automaton, there is an equivalent regular expression that • Reverse Operator
generates the same language. • Prefix Operator
• Suffix operator
• Concatenation
• Union
• Intersection
• Set Difference operator

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Symmetric Difference

RL DCFL CFL CSL RS RES RL DCFL CFL CSL RS RES

Union Y N Y Y Y Y Homomorphism Y N Y N N Y
Intersection Y N N Y Y Y
Complement Y Y N Y Y N ∈ Free Homomorphism
Y N Y Y Y Y
Set Difference Y N N Y Y N
Kleene Closure Y N Y Y Y Y Inverse Homomorphism Y Y Y Y Y Y
Positive Closure Y N Y Y Y Y Substitution
Y N Y N N Y
Concatenation Y N Y Y Y Y
Intersection
with regular set Y Y Y Y Y Y ∈ Free Substitution Y N Y Y Y Y
Reverse Y Y Y Y Y Y
Subset N http://www.knowledgegate.in/gate
N N N N N
Quotient with regular set Y Y Y N
http://www.knowledgegate.in/gate Y Y
Pigeonhole Principle
• The Pigeonhole Principle is a fundamental principle of combinatorial
mathematics that states:
• If n items are put into m containers, with n>m, then at least one container must
contain more than one item.
• This principle seems intuitive, but it has powerful implications and can be used
to prove a variety of seemingly unrelated results across mathematics and
computer science.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Pumping Lemma For Regular Languages Pumping Lemma For Regular Languages
• Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, • For any regular language L, there exists an integer n, such that for all z ∈ L with |z| ≥ n, there
exists u, v, w ∈ Σ∗, such that z = uvw, and
it always satisfies pumping lemma. If there exists at least one string made from pumping
o |uv| ≤ n
which is not in L, then L is surely not regular. o |v| ≥ 1
• The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not o for all i ≥ 0: uviw ∈ L
mean that the language is regular.
• Pumping Lemma is used to prove that some of the language is non-regular. • In simple terms, this means that if a string v is ‘pumped’, i.e., if v is inserted any number of
times, the resultant string still remains in L.
• For the pumping lemma, i/p is NRL & o/p is also NRL.

Pumping Lemma
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Process of pumping Lemma Q Proof that language L = {ambn | m=n} is non-regular?
• Suppose that we need to prove that language L is a non-regular.
• Assume that L is a regular language, then L must satisfy pumping lemma property. L = {ab, aabb, aaabbb, aaaabbbb, ---}
• Choose z ∈ L such that |z| <= n, split z into 3 parts.
o |uv| ≤ n
z∈L
o |v| ≥ 1 Z = ak b k

o If there exist at least one variable for i such that uviw ∉ L, then L does not satisfy pumping
lemma property so it is a contradiction, therefore language L is non-regular. For i=1 à uviw à akbk
For i=2 à uviw à ak+1bk ∉ L

There for L is not regular

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Proof that language L = {ambn | m<n} is non-regular? Q Proof that language L = {anbn | n is a prime number} is non-regular?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Proof that language L = {an^2 | n>= 0} is non-regular?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• SOLVABLE - A problem is said to be solvable if either we can solve it or

PROBLEM if we can prove that the problem cannot be solved

• UNSOLVABLE - A problem is said to be unsolvable if neither we can

SOLVABLE UNSOLVABLE
solve it, nor we can proof that the problem can not be solved

DECIDABLE UNDECIDABLE

P TYPE NP TYPE

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• P- if there exist a polynomial time algorithm to solve a problem then Decision properties
problem is said to be decidable.
• Approximately all the properties are decidable in case a finite automaton. Here
we will use machine model to proof decision properties.
• NP- if there exist a non- polynomial time algo to solve a problem.
i) Emptiness

ii) Non-emptiness

iii) Finiteness

iv) Infiniteness

v) Membership

vi) Equality

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Emptiness & Non-emptiness Finiteness & Infiniteness

• Step 1: - select the state that cannot be reached from the initial states & delete them (remove • Step 1: - Select the state that cannot be reached from the initial state & delete them (remove
unreachable states) unreachable states)
• Step 2: - Select the state from which we cannot reach the final state & delete them (remove
• Step 2: - if the resulting machine contains at least one final states, so then the finite automata dead states)
accepts the non-empty language.
• Step 3: - If the resulting machine contains loops or cycles then the finite automata accepts
• Step 3: - if the resulting machine is free from final state, then finite automata accepts empty infinite language
language. • Step 4: - If the resulting machine do not contain loops or cycles then the finite automata
accepts finite language.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Membership Equality
• Membership is a property to verify an arbitrary string is accepted by a finite automaton or not • Two finite state automata M1 & M2 is said to be equal if and only if, they accept
i.e. it is a member of the language or not.
the same language.
• Let M is a finite automata that accepts some strings over an alphabet, and let ‘w’ be any string
defined over the alphabet, if there exist a transition path in M, which starts at initial state & • Minimise the finite state automata and and the minimal DFA will be unique.
ends in anyone of the final state, then string ‘w’ is a member of M, otherwise ‘w’ is not a
member of M.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

RL DCFL CFL CSL RS RES • Chapter-3 (Regular and Non-Regular Grammars):

Emptiness Y Y Y X N N Context Free Grammar(CFG)-Definition,
Non-Emptiness Y Y Y X N N Derivations, Languages, Derivation Trees and
Finiteness Y Y Y X N N Ambiguity, Regular Grammars-Right Linear and Left
Infiniteness Y Y Y X N N Linear grammars, Conversion of FA into CFG and
Membership Y Y Y X Y N Regular grammar into FA, Simplification of CFG,
Equality Y N N X N N Normal Forms- Chomsky Normal Form(CNF),
Ambiguity Y N N X N N Greibach Normal Form (GNF), Chomsky Hierarchy,
∑* Y N N X N N Programming problems based on the properties of
Halting Y http://www.knowledgegate.in/gate
Y Y X Y N CFGs. http://www.knowledgegate.in/gate
Introduction Formal Grammar
• Language usually contains infinite number of strings. A phrase-structure grammar (or simply a grammar) is a 4-tuple (VN, ∑, P, S), where
• VN is a finite nonempty set whose elements are called variables,
• We cannot tabulate each and every string to represent the language, therefore
like automata, grammar is also a mathematical model of representing a • ∑ is a finite nonempty set whose elements are called terminals, VN ⋂ ∑= Ф.
language, using which we can generate the entire language.
• S is a special variable (i.e., an element of VN (S Î Vn)) called the start symbol. Like every
• Therefore, a grammar is usually thought of as a language generator. automaton has exactly one initial state, similarly every grammar has exactly one start symbol.
• P is a finite set whose elements are α → β. where α and β are strings on VN ⋃ ∑. α has at least
one symbol from VN, the element of P are called productions or production rules or rewriting
rules. {Σ U Vn}* some writer refers it as total alphabet

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

For a formal valid production

αàβ

α Î {Σ U Vn}* Vn {Σ U Vn}*
β Î {Σ U Vn}*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Some points to note about productions Defining a language by grammar
• Reverse substitution is not permitted. For example, if S → AB is a production, • The concept of defining a language using grammar is, starting from a start symbol using the
then we can replace S by AB but we cannot replace AB by S. production rules of the grammar any time, deriving the string. Here every time during
derivation a production is used as its LHS is replaced by its RHS, all the intermediate
• No inversion operation is permitted. For example, if S → AB is a production, it is stages(strings) are called sentential forms. The language formed by the grammar consists of all
not necessary that AB →S is a production. distinct strings that can be generated in this manner.

L (G) = {w | w Î ∑* , S à* W}

• à*(reflexive, transitive closure) means from s we can derive w in zero or more steps

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Using same idea, we do processing of natural languages in computers, Actively Chomsky Classification of Languages
used in compliers
• Chomsky classified the grammars into four types in terms of productions (types 0-3).
• L (G) is the set of all terminal strings derived from the start symbol S. • This hierarchy of grammars was described by Noam Chomsky in 1956. From type 0 to type 3,
we will be putting more and more restrictions.
• G1 and G2 are equivalent if L (G1) = L (G2).
• We will see that more restrictive is grammar easy will be the language and more liberal is the
grammar difficult will be the language. Based on the production rules of the grammar, we can
classify the formal grammar into four types, based on which we generate different languages.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Avram Noam Chomsky (born December 7, 1928) is an American linguist, philosopher, cognitive • An outspoken opponent of U.S. involvement in the Vietnam War, which he saw as an act of American
scientist, historian, social critic, and political activist. Sometimes called "the father of modern linguistics", imperialism, in 1967 Chomsky rose to national attention for his anti-war essay "The Responsibility of
Intellectuals".
• Chomsky is also a major figure in analytic philosophy and one of the founders of the field of cognitive science. He
• Associated with the New Left, he was arrested multiple times for his activism and placed on
is Laureate Professor of Linguistics at the University of Arizona and Institute Professor Emeritus at
President Richard Nixon's Enemies List. While expanding his work in linguistics over subsequent
the Massachusetts Institute of Technology (MIT), and is the author of more than 150 books on topics such as
decades, he also became involved in the linguistics wars. In collaboration with Edward S. Herman,
linguistics, war, politics, and mass media. Ideologically, he aligns with anarcho-syndicalism and libertarian
Chomsky later articulated the propaganda model of media criticism in Manufacturing Consent and
socialism.
worked to expose the Indonesian occupation of East Timor.
• Born to Jewish immigrants in Philadelphia, Chomsky developed an early interest in anarchism from alternative • His defense of freedom of speech, including Holocaust denial, generated significant controversy in
bookstores in New York City. He studied at the University of Pennsylvania. During his postgraduate work in the Faurisson affair of the 1980s. Since retiring from MIT, he has continued his vocal political activism,
the Harvard Society of Fellows, Chomsky developed the theory of transformational grammar for which he earned including opposing the 2003 invasion of Iraq and supporting the Occupy movement. Chomsky began
his doctorate in 1955. That year he began teaching at MIT, and in 1957 emerged as a significant figure in teaching at the University of Arizona in 2017.
linguistics with his landmark work Syntactic Structures, which played a major role in remodeling the study of
language. • One of the most cited scholars alive, Chomsky has influenced a broad array of academic fields. He is
widely recognized as having helped to spark the cognitive revolution in the human sciences, contributing
• From 1958 to 1959 Chomsky was a National Science Foundation fellow at the Institute for Advanced Study. He to the development of a new cognitivistic framework for the study of language and the mind.
created or co-created the universal grammar theory, the generative grammar theory, the Chomsky hierarchy, and
the minimalist program. Chomsky also played a pivotal role in the decline of linguistic behaviorism, and was • In addition to his continued scholarship, he remains a leading critic of U.S. foreign
particularly critical of the work of B. F. Skinner. policy, neoliberalism and contemporary state capitalism, the Israeli–Palestinian conflict, and
mainstream news media. Chomsky and his ideas are highly influential in the anti-capitalist and anti-
http://www.knowledgegate.in/gate imperialist movements. http://www.knowledgegate.in/gate

LANGUAGES AND AUTOMATA Type 0 Grammar

• Following are the machines that accepts the following grammars.
• Also known as Unrestricted Grammar, phase structured grammar, recursively enumerable
grammar used to generate recursive enumerable language which is accepted by a Turing
machine.

• A type 0 grammar is without any restrictions.

• No restriction on the production rule, that is if there is a production from

αàβ
α Î {Σ U Vn}* Vn {Σ U Vn}*
β Î {Σ U Vn}*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Type 1 Grammar • As from the rule we can understand that we cannot have null production, in order to solve that
• Also known as case sensitive Grammar, length increasing grammar, non-contracting grammar, problem, Production SàÎ, is allowed if S do not appear on the right-hand side of the
used to generate context sensitive language which is accepted by a linear bounded production.
automaton.
• A grammar is called type 1 or context-sensitive or context dependent if all its productions are
type 1 productions.
αAβàαδβ
α , β Î {Σ U Vn}* A Î Vn δ Î {Σ U Vn}+ • Very difficult to have a parse tree

or • FORTRAN, PL1 with CGF we use STD

αàβ
α Î {Σ U Vn}* Vn {Σ U Vn}*
β Î {Σ U Vn}+
|α| <= |β|

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Type 2 Grammar Type 3 Grammar

• Also known as Context Free Grammar, which will generate context free language that will be
accepted by push down automata. (NPDA default case) • Used to generate Regular Grammar which will generate regular language which will be
accepted by finite machine.
• if there is a production, from • Regular grammar can be of two types either left linear or right linear.
αàβ • Left regular grammar, support two types of production
A à a / Ba
α Î Vn |α| = 1
A, B Î Vn |A| = |B| = 1
β Î {Σ U Vn} * a Î ∑*
• Right regular grammar
• In other words, the L.H.S. has no left context or right context. A à a / aB
A, B Î Vn |A| = |B| = 1
• A grammar is called a type 2 grammar if it contains only type 2 productions. a Î ∑*
• however, if left-linear rules and right-linear rules are combined, the language need no longer
• Eg ALGOL 60, PASCAL be regular.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Consider the following grammar and identify it’s language? Q Consider the following grammar and identify it’s language?
S à aAb S à AB / Bb

A à aB / b Aàb/c

Bàc Bàd

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Consider the following grammar and identify it’s language? Q Consider the following grammar and identify it’s language?
S à aSb / Î S à aA / abS

A à bS / b

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Consider the following grammar and identify it’s language? Q Consider the following grammar and identify it’s language?
S à aAB S à AB

A à aA / Î A à aA / Î

Bàb B à bB / b

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Consider the following grammar and identify it’s language? Q Design a grammar that generates all strings over the alphabet ∑ = {a,
b}, where every accepted string ‘w’ starts with substring s = abb
S à aSa / bSb / Î

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a grammar that generates all strings over the alphabet ∑ = {a, b}. Q Design a grammar that generates all strings over the alphabet ∑ = {a,
where every accepted string ‘w’ ends with substring s = bab b}. where every accepted string ‘w’ contains sub string s = aba

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a grammar that generates all strings over the alphabet ∑ = {a, Q Design a grammar that generates all strings over the alphabet ∑ = {a, b}, such
b} such that every accepted string start and end with a. that every string ‘w’ accepted must be like
i) |w| = 3 ii) |w|<=3 iii) |w|>=3

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a grammar that generates all strings over the alphabet ∑= {a, Q Design a grammar that generates all strings over the alphabet ∑= {a,
b}, such that every string ‘w’ where |W| = 0(mod 3)? b}, such that every string ‘w’ where |W| = 3(mod 4)?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

S à 01S / 01

Regular Grammar
to
Regular Expression

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
S à 0011S / 01 / 10 S à 01A / B11
A à011A / 01
B à 101B / 11

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

S à 011A / 101B
A à110A / 00
B à 11B / S
Regular Grammar
to
(Finite Automata)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
S à 01S / 1 S à 011S / 01

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

S à 001S / 10A
A à 101A / 0 / 1

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Derivation: - The process of deriving a string is known as derivation. • Sentential form: - Intermediate step involve in the derivation is known
as sentential form.
• Derivation/ Syntax/ Parse Tree: - The graphical representation of
derivation is known as derivation tree. E à E + E / E * E / E = E / id
E à E + E / E * E / E = E / id Sentential Form
E
E*E
E+E*E
ID+E*E
ID+ID*E
ID+ID*ID
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Left most derivation: - the process of construction of parse tree by expanding • Right most derivation: - the process of construction of parse tree by expanding
the left most non terminal is known as LMD and the graphical representation of the right most non terminal is known as RMD and the graphical representation
LMD is known as LMDT (left most derivation tree) of RMD is known as RMDT (right most derivation tree)

LMD RMD
EàE+E E EàE+E E
Eà E * E E*E Eà E * E E+E
Eà E = E E+E*E Eà E = E E+E*E
Eà id ID+E*E Eà id E+E*ID
Eà id ID+ID*E Eà id E+ID*ID
Eà id ID+ID*ID Eà id ID+ID*ID

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Ambiguous grammar: - The grammar CFG is said to be ambiguous if
there are more than one derivation tree for any string i.e. if there exist
more than one derivation tree (LMDT or RMDT), the grammar is said to
be ambiguous.
S à aS/Sa/a

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Unambiguous grammar: - The CFG is said to be unambiguous if there • Some CFL are called inherently ambiguous means there exist no unambiguous
exist only one parse tree for every string i.e. if there exist only one LMDT CFG to generate the corresponding CFL, proved by Rohit Parikh 1961,
or RMDT, then the grammar is unambiguous e.g.
• {a b c d } U {a b c d }
n m m n n n m m

S à aSb/ab

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Grammar which is both left and right recursive is always ambiguous, Simplification or Minimization of CFG
but the ambiguous grammar need not be both left and right recursive.
• The reason we simplify CFG to make it more efficient and compiler friendly.
• The process of deleting and eliminating of useless symbols, unit production and
null production is known as simplification of CFG.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Removal of Null or Empty productions S à AB

• The production of the form A à Î is known as null production of empty Aàa/Î
production, here we try to remove them by replacing equivalent derivation.
Bàb/Î
S à AbB
Aàa/Î
Bàb/Î

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
S à aSb / Î Removal of unit productions

• The production of the form A à B where A, B Î Vn, |A| = |B| = 1, is known as

unit production.

S à Aa
Aàa/B
Bàd

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

S à aAb S à aSb / Î
AàB/a
BàC/b
CàD/c
Dàd

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Removal of useless symbols S à aAB / bA / aC
• The variables which are not involved in the derivation of any string is known as A à aB / b
useless symbol.
• Select the Variable that • Select variable that are B à aC / d
cannot be reached from reachable from the start
the start symbol of the symbol but which does
grammar and remove them not derive any terminal,
along with their all remove them along with
production. their productions

S à aAB S à aA / aB
Aàa Aàb
Bàb
Càd
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Chomsky Normal Form • Avram Noam Chomsky (born December 7, 1928) is an American linguist,
philosopher, cognitive scientist, historian, social critic, and political activist. Sometimes
called "the father of modern linguistics",
• The Grammar G is said to be in Chomsky Normal Form, if every
production is in the form

A à BC / a

B, C Î Vn
aÎS

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
S à aSb / ab S à aAb / bB
Aàa/b
Bàb

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• if CFG is in CNF, then for a derivation of string w, with length we need Greiback Normal Form
exactly 2n -1 production. |w| = n, number of sentential forms will be • The Grammar G is said to be in Greiback Normal Form, if every
2n -1 production is in the form
A à aα

A Î Vn
aÎS
α Î Vn*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
S à aSb / ab
• Sheila Adele Greibach (born 6 October
1939 in New York City) is a researcher in
formal languages in computing, automata,
compiler theory and computer science.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

S à aAb / bB • if CFG is in GNF, then for a derivation of string w, with length we need
exactly n production. |w| = n, number of sentential forms will be n
Aàa/b
Bàb

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Chapter-4 (Push Down Automata and Properties of CONTEXT-FREE LANGUAGES AND PUSH DOWN AUTOMATA
Context Free Languages): Nondeterministic Pushdown • Context-free languages are applied in parser design.
Automata (NPDA)- Definition, Moves, A Language • They are also useful for describing block structures in programming languages.
Accepted by NPDA, Deterministic Pushdown
Automata(DPDA) and Deterministic Context free
Languages(DCFL), Pushdown Automata for Context Free
Languages, Context Free grammars for Pushdown
Automata, Two stack Pushdown Automata, Pumping
Lemma for CFL, Closure properties of CFL, Decision
Problems of CFL, Programming problems based on the
properties of CFLs.
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Push Down Automata BLOCK DIAGRAM OF PDA

• Finite control unit is also called as memory unit it is static and limited. So to process the i/p
• We Already understand the limitation of finite automata, that it cannot do the infinite comparison
between the symbols. string if the static memory is not sufficient then we can use the stack.

• Let us consider L = {an bn | n >= 1}. This is not regular, as it has to remember the number of a's in a • i/p tape is divided into cells where is cell is capable of holding one symbol at a time. At stack of
string and so it will require an infinite number of states, which is logically not possible. infinite size, which support three operations push, pop and skip.
• This difficulty can be avoided by adding an auxiliary memory in the form of a 'stack'. The reason we • The accepting power of a pda is more than that of finite automata and less than that of linear
choose stack because it is the simplest memory possible. bounder automata
• This type of arrangement where a finite automaton has a stack leads to the generation of a • The power of non-deterministic pda is more than the power of deterministic pda.
pushdown automaton.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Formal Definition of DPDA Representation of States
(1) PUSH – one symbol can be inserted into the stack at one time.
A DPDA is a 7-tuple, namely (Q, ∑, Γ, δ, q0, Z0, F), where
δ(qi, a, z0) = (qj, az0)
(i) Q – is a finite nonempty set of states,
(ii) ∑ – is a finite nonempty set of input symbols,
(iii) Γ – is a finite nonempty set of pushdown symbols,
(iv) q0 – is a special state called the initial state,
(v) Z0 – is a special pushdown symbol called the initial symbol on the pushdown store.
(vi) F – is a set of final states, a subset of Q and
(vii) δ – is a transition function from Q x (∑ U {∈}) x Γ to the set of finite subsets of Q x Γ*.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Representation of States Representation of States

(2) POP – one symbol can be deleted from the stack at one time. (3) SKIP – IT means no stack operation, status of the stack will remain same, before
δ(qi, a, z0) = (qj, ε) a after the operation
δ(qi, a, z0) = (qj, z0)

note- if pda perform a push or a pop operation at least one’s during processing of
string than we say that pda is using the stack.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Instantaneous Description (ID) ACCEPTANCE BY PDA

• An instantaneous description (ID) is (q, x, α), where q ∈ Q, x ∈ ∑* and α ∈ Γ*.

• There is no change in the language acceptance capability of the pda either we
accept by final state of empty stack.
• An initial ID is (q0, x, Z0), this means that initially the pda is in the initial state q0, the input
string to be processed is x and the PDS has only one symbol, namely Z0.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a Deterministic Push Down Automata for {an bn | n >= 1} ? Q Design a Deterministic Push Down Automata for {an b2n | n >= 1} ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a PDA for {w c wr | w ∈(a, b)*} ? Q Construct PDA that accepts L = {|w|a = b | w € (a, b)*} ?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Non- Deterministic PDA Q Construct pda that accepts a language L = {w wr | w € (a, b)*}?
• Non- Deterministic PDA can also be defined using 7 tuples.
• δ: Q x {∑ U ∈} x Γ → 2(Q x Γ* )
• i.e. on a given input symbol and stack symbol a NPDA can move to more than one state.
• Rest all other tuples are same as DPDA.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Decision properties Q consider the following CFG and identify which of the following CFG generate Empty language?

Following properties are decidable in case a CFL. Here we will use Grammar model
S à aAB / Aa
to proof decision properties.
Aàa
i) Emptiness
S à aAB
ii) Non-emptiness
Aàa/b
iii) Finiteness
S à aAB / aB
iv) Infiniteness A à aBb
B à aA
v) Membership

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q consider the following CFG and identify which of the following CFG generate Finite Q consider the following CFG and check out the membership properties?
language?

S à SS / AB S à AB / BB
A à BC / a
B à CC / b A à BA / AS / b
B à AA / SB / a
S à AB
AàB/a w1 = aba
w2 = abaab
S à AB
A à BC / a w3 = abababba
B à CC / b
C à AB
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
CYK algorithm Following properties are Undecidable in case a CFL
i) Equality
• In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is
a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger
and Tadao Kasami. It employs bottom-up parsing and dynamic programming. ii) Ambiguity
• The standard version of CYK operates only on context-free grammars given in Chomsky normal
form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the
same language (Sipser 1997).

• The importance of the CYK algorithm stems from its high efficiency in certain situations. Using Big O
notation, the worst case running time of CYK is O (n3 .|G|), Where n is the length of the parsed string
and |G| is the size of the CNF grammar G.

• This makes it one of the most efficient parsing algorithms in terms

of worst-case asymptotic complexity, although other algorithms exist
with better average running time in many practical scenarios.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

RL DCFL CFL CSL RS RES Closure Properties of Deterministic Context Free Languages
• Deterministic Context Free Languages are closed under following operations
Emptiness Y Y Y X N N • Complement
• Intersection with regular set
Non-Emptiness Y Y Y X N N • Inverse Homeomorphism

Finiteness Y Y Y X N N • Deterministic Context Free Languages are not closed under following operations
• Union
Infiniteness Y Y Y X N N • Concatenation
• Kleen closure
Membership Y Y Y X Y N • homomorphism
• Substitution
Equality Y N N X N N • Reverse operator
• Intersection
Ambiguity Y N N X N N
∑* Y N N X N N
Halting Y http://www.knowledgegate.in/gate
Y Y X Y N http://www.knowledgegate.in/gate
Closure Properties of Context Free Languages RL DCFL CFL CSL RS RES
• Context Free Languages are closed under following operations
• Union
Union Y N Y Y Y Y
• Concatenation
• Kleen Closure
Intersection Y N N Y Y Y
• Substitution Complement Y Y N Y Y N
• Homomorphism
• Inverse Homomorphism Set Difference Y N N Y Y N
• Reverse Operator
• Intersection with regular set Kleene Closure Y N Y Y Y Y
• Context Free Languages are not closed under following operations Positive Closure Y N Y Y Y Y
• Intersection
• Complement Concatenation Y N Y Y Y Y
• Symmetric Difference
Intersection with
regular set Y Y Y Y Y Y
Reverse Y Y Y Y Y Y
Subset N N N N N N
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

RL DCFL CFL CSL RS RES

• Chapter-5 (Turing Machines and Recursive Function
Homomorphism Y N Y N N Y Theory): Basic Turing Machine Model, Representation of
Turing Machines, Language Acceptability of Turing
∈ Free Homomorphism
Y N Y Y Y Y Machines, Techniques for Turing Machine Construction,
Inverse Homomorphism Y Y Y Y Y Y Modifications of Turing Machine, Turing Machine as
Computer of Integer Functions, Universal Turing
Substitution
Y N Y N N Y machine, Linear Bounded Automata, Church’s Thesis,
∈ Free Substitution Y N Y Y Y Y Recursive and Recursively Enumerable language, Halting
Problem, Post’s Correspondance Problem, Introduction
Quotient with regular set Y Y Y N Y Y to Recursive Function Theory.
http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Turing Machine • Turing machines are useful in several ways:
• The Church-Turing thesis states that any algorithmic procedure that can be carried out by human
beings/computer can be carried out by a Turing machine. • As an automaton, the Turing machine is the most general model.

• It has been universally accepted by computer scientists that the Turing machine provides an ideal theoretical • It accepts type-0 languages.
model of a computer.
• It can also be used for computing functions.
• Turing machines are also used for determining the undecidability of certain languages
and measuring the space and time complexity of problems.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Components of Turing Machine Components of Turing Machine

Infinite Tape Read-Write Buffer
• An input infinite tape can be, used as an input buffer and also as a member element. • Read the data from the tape and can also write the data over the tape. After reading the
• It is random accessible. It is of infinite length divided into cells and each cell is capable of symbol from the tape, the read/write header moves to exactly one cell either in left or
holding only one tape symbol. right direction.
• It is also called 2-way infinite tape.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Components of Turing Machine FORMAL DEFINITION
Finite Control Unit
• As per the control unit, the transitions will take place, and will finally lead to some output. A Turing machine M is a 7-tuple, namely (Q, ∑, Γ, δ, q0, b, F), where
• Q is a finite nonempty set of states.

• Γ is a finite nonempty set of tape symbols,

• b ∈ Γ is the blank.

• ∑ is a nonempty set of input symbols and is a subset of Γ and b ∉∑.

• δ is the transition function mapping d: Q ×ℾ -> Q× ℾ × (L/R). It says that, on providing a tape symbol, from a
particular state there will be a transition to another state, with a different or same tape symbol with defining
whether next the machine needs to move in left/ right.

• q0 ∈ Q is the initial state, and

• F ⊆ Q is the set of final states.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a Turing machine for L = {an bn | n >= 1}? REPRESENTATION OF TURING MACHINES

Three representations:
• Instantaneous descriptions using move-relations.
• Transition table, and
• Transition diagram (transition graph).

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
LANGUAGE ACCEPTABILITY BY TURING MACHINES
Q Design a Turing machine for L = {an bn cn| n >= 0}?
• A string w in ∑* is said to be accepted by a TM(M) if after parsing the string w Turing machine
must halts on final state.
• q0w ⊢* α1pα2 for some p ∊ F and α1, α2 ∊ Γ *.
• M does not accept w if the machine M either halts in a non-accepting state or does not halt
and goes into a loop.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Q Design a Turing machine for L = {w c w | w ∊ {0, 1}* }? Q Design a Turing machine for addition of two number in unary?

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Q Design a Turing machine for converting unary number into binary
number?

Versions of Turing Machine

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• On the basis of determinism of the next transition to a state on a particular Versions of Turing Machine
input, Turing Machine are divided in two types- • There are multiple versions of Turing Machine which are as follows-
• Determinism Turing Machine.
• Non-Deterministic Turing Machine. • Multi-tape Turing Machine.
• In multi-tape Turing machine, there can be more than one tape and corresponding head
pointers, but it does not add any power to Turing machine.
• In non-deterministic Turing machine, there can be more than one possible move • Every multi-tape TM can be converted into single tape TM.
for a given state and tape symbol, but non-deterministic TM does not add any • Every language accepted by a multi-tape TM is acceptable by some single-tape TM (that is,
power. the standard TM).
• Every non-deterministic TM can be converted into deterministic TM. • Multi Read/Write head points.
• Multi-dimensional Turing Machine.
• TM with stay option d: Q ×ℾ -> Q× ℾ × (L/R/S).
• TM with one way infinite tape (Semi infinite tape)

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
• Offline TM, this TM have a restriction that input can not be changed Q Consider the Turing machine M defined below 0 1 B
Choose the false statement ® Q0 (Q0, 0, R) (Q2, 1, L) (Qf, -, -)
• Jumping TM, where it is allowed to take more that one moves in one transaction d: Q ×ℾ -> Q×
a) The machine loops on 01 Q1 (Q2, 1, L) (Q1, 1, R) (Qf, -, -)
ℾ × (L/R) ×{n}.
Q2 (Q2, 1, L) (Q2, 0, L) (Qf, -, -)
• Non erasing TM, (where input can not be converted to blank) b) The machine does not accept 0000
*Qf --- --- ---
• Always writing TM, (after reading a symbol from tape it must be replaced with other symbol)
c) The machine accepts strings ending with a 1
• Multidimensional TM d: Q ×ℾ -> Q× ℾ × (L/R/U/D)
• Multi-head TM d) The machine accepts strings ending with 10
• FA with a Queue
• TM with only 3 states
• Multi-tape Turing Machine with stay option and at most 2 states.
• Non-Deterministic TM d: Q ×ℾ -> 2 Q× ℾ × (L/R)
• A NPDA with two independent stacks d: Q ×(S U Î) × ℾ × ℾ -> 2 Q× ℾ* × ℾ*

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Halt • So, broadly Recursively Enumerable Languages are categorized as-

• Recursive Set- The Language L, which is accepted by Turing Machine, is said to be recursive
• The state of Turing machine, where no transition is defined or required is known as Halt. There set, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’ that
are two types of Halt- does not belongs to L, machine will go to non-final halt. Hence, membership property is
• Final Halt- Machine has been halted on final state, then it is known as Final halt and hence defined here.
it depicts that machine is accepted. • Recursively Enumerable Set- The language L, which is accepted by Turing Machine is said
• Non-Final Halt-Machine has been halted on non- final state, then it is known as non- final to be REL, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’
halt and hence the string is rejected. that does not belongs to L, machine will either go to non-final halt or infinite loop. Hence,
membership property is not defined here.
• After taking an input string, there are three possibilities for Turing Machine
• It may go to Final halt. • If a set and its complement both are recognizable, then the set is decidable.
• It may go to Non- Final halt. • There are some sets which are not recognizable (even members can’t be identified) because
• It may go into Infinite loop. there are more languages than programs.

• Final Halt and Non- Final Halt have been described above. After taking an input string, if the
machine goes to infinite loop, then we can’t say whether the string is Accepted/Rejected.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Universal Turing Machine

• In computer science, a universal Turing machine (UTM) is a Turing machine that

simulates an arbitrary Turing machine on arbitrary input.

Universal Turing Machine • The universal machine essentially achieves this by reading both the description
of the machine to be simulated as well as the input to that machine from its own
tape.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

• Every Turing machine computes a certain fixed partial computable function from the input
strings over its alphabet. In that sense it behaves like a computer with a fixed program.

• However, we can encode the action table of any Turing machine in a string. Thus we can
construct a Turing machine that expects on its tape a string describing an action table followed
by a string describing the input tape, and computes the tape that the encoded Turing machine
would have computed. Turing described such a construction in complete detail in his 1936
paper:

• "It is possible to invent a single machine which can be used to compute any computable
sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D
["standard description" of an action table] of some computing machine M, then U will
compute the same sequence as M.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
A Linear Bounded Automaton (LBA) is similar to Turing Machine with
property stated below:
•Turing Machine with a bounded finite length of the tape.

Linear Bounded Automata

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Turing-Church Thesis 1.Turing Machines: Turing proposed the concept of a 'Turing machine', a
• Concept Origin: Independently developed by Alan Turing and Alonzo Church in theoretical computing machine that can simulate any algorithm's logic.
the 1930s, establishing a fundamental principle in computer science about
computable functions. 2.Church's Lambda Calculus: Church introduced lambda calculus, a
formal system for expressing computation based on function abstraction
and application.

3.Equivalent Models: The thesis states that what can be computed on a

Turing machine can also be computed in Church's lambda calculus,
implying both models are equivalent in their computational power.

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
The Post Correspondence Problem (PCP) • Undecidability: The Post Correspondence Problem is known to be undecidable,
meaning there is no algorithm that can determine for every instance of the
• is a significant problem in the field of theoretical computer science. It was introduced by Emil
Post in 1946 and is known for its undecidability. Here are the main points: problem whether or not a solution exists. This undecidability is a crucial aspect
in the theory of computation, particularly in understanding the limits of
• Basic Concept: The problem involves two lists of words (strings of symbols) over a
common alphabet. The challenge is to find a sequence of indices where the concatenation
algorithmic solvability.
of the words in the first list, in that sequence, is equal to the concatenation of the words in
the second list in the same sequence.
• A = {b, babbb, ba}
• A = {1, 110, 0111} • B = {bbb, ba, a}
• B = {111, 001, 11}

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

Decision properties RL DCFL CFL CSL RS RES

Emptiness Y Y Y X N N

• Following properties are decidable in case a RS. Non-

Y Y Y X N N
Emptiness
• Membership
Finiteness Y Y Y X N N

Infiniteness Y Y Y X N N
• All properties are undecidable in case of a REL.
Membershi
Y Y Y X Y N
p
Equality Y N N X N N

Ambiguity Y N N X N N

∑* Y N N X N N

Halting Y Y Y X Y N

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate
Closure Properties of Recursive Set Closure Properties of Recursive Enumerable Set
• Recursive languages are closed under following operations • Recursive Enumerable are closed under following operations
• Union • Union
• Concatenation • Concatenation
• Intersection • Kleen Closure
• Reverse • Intersection
• Complement • Substitution
• Inverse homomorphism • Homomorphism
• Intersection with regular set • Inverse Homomorphism
• Set Difference
• Intersection with regular set
• Reverse operation
• Recursive languages are not closed under following operations
• Kleen closure
• Homomorphism • Recursive Enumerable are not closed under following operations
• Substitution • Compliment
• Set Difference

http://www.knowledgegate.in/gate http://www.knowledgegate.in/gate

RL DCFL CFL CSL RS RES RL DCFL CFL CSL RS RES

Union Y N Y Y Y Y
Homomorphism Y N Y N N Y
Intersection Y N N Y Y Y

Complement Y Y N Y Y N
∈ Free Homomorphism
Y N Y Y Y Y

Set Difference Y N N Y Y N

Kleene Closure Y N Y Y Y Y
Inverse Homomorphism Y Y Y Y Y Y

Positive Closure Y N Y Y Y Y
Substitution
Y N Y N N Y
Concatenation Y N Y Y Y Y

Intersection with
Y Y Y Y Y Y
∈ Free Substitution Y N Y Y Y Y
regular set

Reverse Y Y Y Y Y Y
Quotient with regular set Y Y Y N Y Y
Subset N http://www.knowledgegate.in/gate
N N N N N http://www.knowledgegate.in/gate