TCS Notes

Chapter 1

1.1 Formal Definition of a DFA:

A DFA is a 5-tuple (Q, Σ, δ, q0, F) where:

Q: Finite set of states (e.g., S1, S2, S3)

Σ: Finite alphabet of symbols (e.g., 0, 1, a-z)

δ: Transition function that maps (state, symbol) pairs to next states (e.g., δ(S1,
0) = S2)

q0: Start state (the initial state when processing a string)

F: Set of final states (states indicating successful string recognition)

1.2 Transition Diagram:

Visually represents the states, transitions, and start/final states using nodes and
directed arrows.

1.3 Language Recognition by a DFA:

The DFA reads a string one symbol at a time, transitioning between states based
on the transition function.

If the DFA reaches a final state after reading the entire string, it accepts the string
(belongs to the language recognized by the DFA).

If the DFA reaches a non-final state at any point, it rejects the string.

1.4 Examples of DFAs:

Recognizing strings that end in "01":

States: q0 (start), q1, q2 (final)

Alphabet: {0, 1}

TCS Notes 1
 Transitions: δ(q0, 0) = q0, δ(q0, 1) = q1, δ(q1, 0) = q2

Recognizing strings with an even number of 0s:

States: q0 (start), q1

Alphabet: {0, 1}

Transitions: δ(q0, 0) = q1, δ(q0, 1) = q0, δ(q1, 0) = q0, δ(q1, 1) = q1

1.5 Operations on Languages:

Union: Combine two languages (strings accepted by either DFA)

Intersection: Only accept strings recognized by both DFAs

Complement: Accept strings rejected by the original DFA

1.6 Limitations of DFAs:

Cannot recognize languages requiring "memory" of past symbols (e.g., balanced
parentheses)

1.7 Nondeterministic Finite Automata (NFA):

NFA introduce non-determinism, allowing multiple transitions from a state for a single
symbol or even the potential to stay in the same state. This increases their
expressive power compared to DFAs, enabling them to recognize certain languages
beyond DFAs' capabilities.
Formal Definition:

An NFA is a 5-tuple (Q, Σ, δ, q0, F) similar to a DFA, but with:

δ: Transition function that maps (state, symbol) pairs to a set of next states
(including possibly empty).

Properties:

An NFA accepts a string if there exists at least one path through its states,
reading the symbols in order, that ends in a final state.

Any language recognized by a DFA can also be recognized by an NFA (but not
vice versa).

Examples:

TCS Notes 2
 Recognizing strings with an even number of 0s or ending in "01":

Same states and alphabet as the DFA examples.

Transitions: δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0}, δ(q1, 0) = {q0, q1}, δ(q1, 1) =
{q1}

Recognizing balanced parentheses "(){}" (not possible with a DFA):

States: q0 (start), q1, q2 (final)

Alphabet: {(, ), }

Transitions: δ(q0, "(") = {q1}, δ(q1, ")") = {q2}, δ(q1, "(") = {q1}, δ(q2, ε) = {q2}
(ε denotes the empty string)

1.8 Comparison of NFA & DFA:

Here's a table summarizing the key differences between NFAs and DFAs:

Deterministic Finite Automaton Nondeterministic Finite

Feature
(DFA) Automaton (NFA)

Always unique for each state- Can be non-deterministic (multiple

Transitions
symbol pair options)

Expressive Less expressive (cannot More expressive (can recognize

Power recognize balanced parentheses) languages beyond DFAs)

Can be harder to analyze and

Complexity Easier to analyze and implement
implement (finding accepting paths)

Formal Not always equivalent to regular Can be equivalent to regular

Equivalence expressions expressions

DFAs can be converted to

Converting NFAs to equivalent DFAs
Conversion equivalent NFAs (but not vice
can be complex
versa)

1.9 Myhill-Nerode Method:

This technique helps minimize the number of states in a DFA while preserving its
language recognition capability. It works by grouping states based on strings they
both accept or reject. By iteratively merging equivalent groups, a minimal DFA is
obtained.

TCS Notes 3
 1.10 Mealy and Moore Machines:
These are variations of DFAs that output symbols or take actions during transitions.

Mealy Machines: Outputs depend on the current state and input symbol.

Moore Machines: Outputs depend only on the current state.

1.11 Minimization of DFAs:

Minimizing a DFA involves reducing the number of states it has while still recognizing
the same language. This can be achieved with algorithms like:

Hopcroft's Minimization Algorithm: This iterative process identifies equivalent

states based on their behavior (accepted and rejected strings) and merges them,
resulting in a minimal DFA.

Moore's Minimization Algorithm: Similar to Hopcroft's, but uses distinguishable

pairs of states to achieve minimization.

Minimization reduces the complexity of the DFA, making it easier to analyze and
implement.

1.12 Applications of Finite Automata:

Finite automata have various applications in computer science and beyond,
including:

Lexical analysis: Tokenizing input in compilers and interpreters.

Text processing: Pattern matching and searching for specific sequences.

Hardware design: Controlling the behavior of digital circuits.

Network protocols: Parsing communication messages and verifying their

validity.

Bioinformatics: Modeling genetic sequences and protein structures.

Chapter 2 : Regular Expressions and

Languages

2.1 Regular Expressions (REs):

TCS Notes 4
 A concise and powerful notation for describing formal languages recognized by
Finite Automata.

Built using basic symbols like letters, digits, special characters, and operators
like union, concatenation, and repetition.

2.2 Basic RE Operators:

Union (|): Combines two REs, accepting strings belonging to either language.

Concatenation (•): Joins two REs, requiring both patterns to appear

consecutively in the accepted strings.

Kleene Star (*): Zero or more repetitions of the preceding RE symbol.

Kleene Plus (+): One or more repetitions of the preceding RE symbol.

Question Mark (?): Zero or one occurrence of the preceding RE symbol.

2.3 Examples of REs:

a*b : Any string with zero or more "a"s followed by a "b".

(ab)*(ba)* : Any string consisting of alternating blocks of "ab" and "ba".

(0|1)* : Any string containing only 0s and 1s.

2.4 Regular Languages:

A set of strings accepted by a regular expression.

Closed under union, intersection, and complement operations.

2.5 Conversion between REs and Finite Automata:

From RE to FA: Construct an FA that mimics the RE's pattern recognition logic.

From FA to RE: Identify the sequence of operations represented by the FA's

transitions to derive the corresponding RE.

2.6 Pumping Lemma for Regular Languages:

A mathematical property that helps prove whether a language is regular or not.

States that if a language is regular, any sufficiently long string in the language
can be "pumped" (repeated sections) to create new strings still belonging to the

TCS Notes 5
 language.

2.7 Closure Properties of Regular Languages:

Regular languages are closed under:

Union: Combining two regular languages.

Intersection: Selecting strings accepted by both languages.

Complement: Accepting strings rejected by the original language.

Homomorphism: Applying a string-substitution function.

Inverse Homomorphism: Replacing characters with original patterns.

2.8 Applications of Regular Expressions:

Regular expressions have widespread applications in various fields, including:

Text processing: Search and replace, pattern matching, validation, data

extraction.

Compilers and interpreters: Lexical analysis, tokenization, syntax recognition.

Network protocols: Parsing data packets, verifying message formats.

Bioinformatics: Analyzing genetic sequences, searching for protein motifs.

Software testing: Validating input formats, identifying potential errors.

Natural language processing: Tokenization, part-of-speech tagging, regular

expressions are often used as building blocks for more complex language
models.

Understanding how to utilize regular expressions effectively for pattern recognition

and language processing is an essential skill in computer science and related fields.

2.9 Advanced Regular Expression Features:

Beyond the basic operators, REs offer additional functionalities for complex pattern
matching:

Character classes: Specify a set of characters accepted at a specific position

(e.g., [a-z] for any lowercase letter).

Backreferences: Refer to previously matched subpatterns within the

expression.

TCS Notes 6
 Anchors: Match strings only at the beginning or end (e.g., ^pattern$ ).

Negation: Exclude specific characters or patterns from the match.

Possessive quantifiers: Match as many repetitions as possible for a specific

subpattern.

2.10 Examples of Advanced Regular Expressions:

To illustrate the power of advanced features, let's consider some examples:

Matching email addresses: ^([a-zA-Z0-9_\.\+-]+)@([a-zA-Z0-9-]+)(\.[a-zA-Z0-

9-]+)+<span class="math-inline">\ - This RE uses character classes, anchors, and

concatenation to match a valid email address format. * **Extracting URLs from
text:** `https?://(?:www\.)?([a-zA-Z0-9-]+\.)+[a-zA-Z0-9-]+(?:/[^ ]*)?`

This RE incorporates the "non-capturing group" feature to handle optional "www."

and includes capturing groups for the domain and path components.

Validating phone numbers: ^\d{3}[-\.]?\d{3}[-\.]?\d{4}$

This RE defines a flexible format for phone numbers with optional hyphens or
dots and three-digit segments.

Finding repeated words: \b(\w+)\s+\1\b

This RE uses word boundaries and backreferences to identify occurrences of

consecutive words (excluding prepositions like "the").

Chapter 3: Context-Free Grammars and

Languages
3.1 Introduction to Context-Free Grammars (CFGs):
Define CFGs and their components: productions, terminals, non-terminals, start
symbol.

Understand derivation trees and how they represent the generation of strings
from a CFG.

TCS Notes 7
 Compare CFGs with regular expressions in terms of expressiveness and
recognition power.

3.2 Formal Definition of CFGs:

Learn the precise grammatical notation and production rules for describing
languages with CFGs.

Analyze examples of CFGs for languages like balanced

parentheses, palindromes, and arithmetic expressions.

Practice constructing CFGs for simple languages based on their structure and
derivation rules.

3.3 Chomsky Hierarchy and Language Classes:

Explore the different levels of the Chomsky hierarchy, including regular
languages, CFGs, context-sensitive languages, and unrestricted grammars.

Understand the increasing power and complexity of languages at each level in

the hierarchy.

Analyze the limitations of CFGs and their relationship to other language classes.

3.4 Applications of CFGs:

Discover the diverse applications of CFGs in various fields like compiler
construction, parsing natural languages, image processing, and music
composition.

Discuss advanced topics like parsing algorithms, ambiguity in grammars, and

automated grammar generation.

MORE NOTES

1. Grammar:

Defining CFGs and their components: productions, terminals, non-terminals, and

start symbol.

Understanding derivation trees and how they represent the generation of strings
from a CFG.

TCS Notes 8
 Discussing differences between CFGs and regular expressions in terms of
expressiveness and recognition power.

2. Derivation-reduction:

Exploring the process of applying production rules repeatedly to non-terminals in

a string, eventually reaching a terminal string.

Illustrating derivation trees as graphical representations of this process.

Highlighting the importance of derivation-reduction in analyzing and

understanding CFGs.

3. Context-Free Grammer (CFG):

Formalizing the definition of a CFG with terminal and non-terminal symbols, start
symbol, and production rules.

Analyzing examples of CFGs for various languages like balanced

parentheses, arithmetic expressions, and simple programming constructs.

Practicing constructing CFGs based on the structure and derivation rules of

specific languages.

4. Ambiguous Grammer:

Identifying situations where a CFG can generate multiple derivation trees for the
same string, leading to ambiguity.

Understanding the consequences of ambiguity for parsing and interpreting

languages defined by CFGs.

Discussing techniques for detecting and removing ambiguities in grammars.

5. Normal Forms:

Introducing Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) as
special types of CFGs with specific restrictions on production rules.

Explaining the benefits of normal forms in simplifying and analyzing CFGs.

Exploring algorithms for converting CFGs to CNF or GNF.

6. Left Linear and Right Linear Grammer:

Introducing subclasses of regular grammars where all production rules have non-
terminals either at the leftmost or rightmost position.

TCS Notes 9
 Exploring the benefits of left-linear and right-linear grammars for efficient parsing
and analysis of regular languages.

Analyzing examples of languages that can be described by such grammars.

7. Equivalence of FA and Regular Grammar:

Showing that any regular language recognized by a Finite Automaton (FA) can
also be defined by a regular grammar.

Discussing the equivalence between these two models for recognizing simple
patterns and languages.

Understanding the significance of this equivalence in theoretical computer

science.

Grammar of Context-Free Grammars (CFGs).

Remember, a CFG defines a set of strings (languages) through productions, which

replace non-terminal symbols (variables) with strings of terminal symbols (concrete
characters). We'll explore its components:

Terminals: Represent the actual symbols in the generated strings, like

letters, digits, punctuation marks, etc.

Non-terminals: Act as placeholders or variables that can be further expanded

using production rules.

Start Symbol: A designated non-terminal from which the entire derivation

process begins.

Production Rules: These are the core of a CFG, written in the format A ->
α, where A is a non-terminal and α is a string of terminals and/or non-
terminals. They define how non-terminals can be replaced with concrete strings.

To solidify your understanding, let's consider an example CFG for the language of
balanced parentheses:
S -> (S) | () | ε (empty string)

This CFG has one non-terminal (S) and three production rules. These rules tell us:

S can be replaced with either "(S)" (another pair of parentheses), "()", or the
empty string.

By repeatedly applying these rules, starting from S, we can generate strings like
"()", "((()))", "(()())", etc., all of which are balanced parentheses.

TCS Notes 10
 Next, we can explore derivation trees, which visually represent the step-by-step
application of production rules. They start from the start symbol and expand non-
terminals until all nodes contain only terminals.

For example, the derivation tree for the string "()" would look like this:
S
/ \
( )

Here, S is replaced with "()" in the first step, resulting in two terminal leaves
representing the balanced parentheses.

Chomsky Normal Form (CNF) and Greibach Normal Form (GNF) for context-
free grammars (CFGs):
CNF:

A special type of CFG where all production rules follow one of these formats:

A non-terminal symbol is replaced by a single terminal symbol (A -> a).

A non-terminal symbol is replaced by two non-terminal symbols (A -> B C).

This restriction simplifies the structure of the CFG and makes it easier to analyze
and manipulate.

Any CFG can be converted to an equivalent CNF CFG using algorithms like
Chomsky's Normalization Algorithm.

GNF:

Another special type of CFG where all production rules follow one of these
formats:

A non-terminal symbol is replaced by a terminal symbol followed by any

number of non-terminal symbols (A -> aX1X2...Xn).

The start symbol (S) can be replaced by the empty string (epsilon) (S -> ε).

This form focuses on rewriting rules from left to right, making it useful for
parsing algorithms and proving pumping lemmas.

Not all CFGs can be converted to GNF, but a large subset can.

Benefits of normal forms:

Simplify analysis and manipulation of CFGs.

Prove equivalence between different CFGs for the same language.

TCS Notes 11
 Design efficient parsing algorithms.

Examples:

The CFG for balanced parentheses can be converted to both CNF and GNF:

CNF: S -> (S) | () | ε

GNF: S -> (T) | ε, T -> S T | ε

Chapter 4 Pushdown Automata

Pushdown Automata (PDAs):
Definition: A pushdown automaton (PDA) is a more powerful model of computation
than a finite automaton, capable of recognizing context-free languages. They have
the same basic components as finite automata (states, alphabet, transitions) but with
the addition of a stack for storing symbols. This allows PDAs to remember parts of
the input string they have already processed, enabling them to recognize languages
with hierarchical structures.

Types of PDAs:

Deterministic PDA (DPDA): Follows a unique transition function for each state
and input symbol combination.

Nondeterministic PDA (NPDA): May have multiple possible transitions for a

given state and input symbol. NPDAs are more powerful than
DPDAs, recognizing a wider range of languages.

Correlation and Examples of NPDA:

NPDAs can recognize languages with nested structures, like balanced

parentheses (e.g., (((())))) or arithmetic expressions with nested subexpressions.

They can also handle languages with unbounded recursion, like the language of
all strings over {a, b} that end in n consecutive b's, where n is an arbitrary
positive integer.

An example of an NPDA recognizing the language of balanced parentheses:

States: q0 (start), q1, q2 (final)

TCS Notes 12
 Alphabet: {, }, a, b

Stack: (push/pop)

Transition function: defined for various combinations of state, input

symbol, and top of stack

Example transitions: (q0, {, ) -> q1, push }), (q1, a, ( ) -> q1)

CFG (in GNF) to PDA Method:

A Chomsky Normal Form (CNF) context-free grammar can be directly converted

into a PDA by building a transition for each production rule in the grammar.

The states of the PDA correspond to the non-terminals in the grammar, and the
stack stores the remaining non-terminals to be expanded and terminals
processed.

This method provides a direct link between these two models of computation.

Chapter 5 : Turning Machines

Turing Machine Basics:

Definition: A theoretical model of computation with unbounded storage (tape)

and the ability to manipulate symbols, simulating any computable process.

Components:

Tape: An infinite, two-way tape holding symbols representing the input and
working memory.

Head: Reads and writes symbols on the tape, moving left or right.

States: The current "mode" of the machine, determining its next action.

Transition Function: Defines how the machine changes state and

manipulates symbols based on the current state and symbol read.

Operation: The machine starts in a certain state and reads the input on the tape.
Based on the current state and read symbol, it applies the transition function,
potentially changing state, writing a symbol on the tape, and moving the head left
or right. This cycle continues until the machine halts (enters a specific final state).

Turing Machine Power:

TCS Notes 13
 Universal Computation: Church-Turing Thesis states that any computable
function can be implemented by a Turing Machine. This makes them the
theoretical limit of what's computable.

Examples: Recognizing any context-free language, palindromes, arithmetic

expressions, etc.

Turing Machine Limitations:

Undecidable Problems: Certain questions (like the Halting Problem) cannot be

answered definitively by any Turing Machine, showcasing the inherent limitations
of formal systems.

Resource Limitations: Some problems require immense time or space

resources, even for a Turing Machine, hinting at the practical boundaries of
computation.

Applications:

Complexity Theory: Classifying computational problems based on their

resource requirements (time, space).

Cryptography: Designing secure encryption and decryption algorithms based

on principles of Turing Machines.

Artificial Intelligence: Theoretical foundation for understanding and potentially

achieving artificial intelligence.

TCS Notes 14