TOC-UNIT I-II M.SC CS

 

THEORY OF COMPUTATION-(536C3C)

Definition:

to understand the capabilities and limitations of computation by analyzing mathematical models of how machines can perform calculations.

Introduction to Theory of Computation - GeeksforGeeks

UNIT I

Review of Mathematical Theory Combinatorics: Review of Permutation and Combination- Mathematical Induction- Pigeon hole principle- Principle of Inclusion and Exclusion- generating function- Recurrence relations. Statements– Connectives– Truth Tables– Normal forms– Predicate calculus– Inference Theory for Statement Calculus and Predicate Calculus.

1.1)Review Of Mathematical Theory Combinatorics

Mathematical Theory:

A mathematical theory is a systematic and logical framework consisting of a set of axioms, definitions, theorems, and rules that are used to explain and predict mathematical relationships and structures.

Combinatorics:

Combinatorics is a branch of mathematics that deals with counting, arranging, and selecting objects. It provides techniques to find the number of possible configurations or outcomes in a finite set, particularly when order matters (permutations) or doesn’t matter (combinations).

• Permutations: Counting arrangements of objects where order is important.
• Combinations: Counting selections of objects where order is not important.
• Counting Principles: Such as the Addition and Multiplication Rules.
• Advanced Techniques: Including Inclusion-Exclusion, Pigeonhole Principle, and Generating Functions.

1.2)Review of Permutation and Combination

Permutation:

·       Permutation refers to the arrangement of objects where the order matters.

·       When the position or order of the selected items matters, the different ways they can be arranged are called permutations.

permutation plays a key supporting role in the following areas:

📌 1. String Generation in Formal Languages

• Permutations help in generating all possible strings of a certain length using a finite alphabet Σ
• Example: For Σ={a,b} all 2-letter permutations → aa, ab, ba, bb.

1. String Generation in Formal Languages

• Permutations help in generating all possible strings of a certain length using a finite alphabet Σ.
• Example: For Σ={a,b}all 2-letter permutations → aa, ab, ba, bb.

📌 2. Transition Path Enumeration

• In finite automata (DFA/NFA), different permutations of input symbols determine different state transition paths.
• Understanding permutations helps analyze how many distinct paths or configurations an automaton can take.

📌 3. Encoding and Code Design

• Permutations are used in designing encodings (e.g., binary codes, prefix codes in Huffman encoding) where each symbol arrangement carries meaning.

📌 4. State Arrangement and Labelling

• In Turing Machines or Pushdown Automata, permutations of tape symbols or stack symbols are considered while defining transition functions.

📌 5. Complexity and Enumeration Problems

• Permutations are used to calculate the time or space complexity for algorithms that check all possible sequences (e.g., brute-force search).
• Example: For n inputs, checking all orderings → n! permutations.

Example 1:

Q: A DFA has 3 input symbols and accepts strings of length 2. How many unique strings can be formed?

A:

• Permutation with repetition (since symbols can repeat):3^2 = 9 strings

Strings: aa, ab, ac, ba, bb, bc, ca, cb, cc

 

 

Example 2:

If you have 3 letters: A, B, C
The permutations of 2 letters are:
AB, BA, AC, CA, BC, CB → Total = 6 permutations

Let’s say we have 3 letters: A, B, C

Permutations of 2 Letters (Without Repetition):

First Letter	Second Letter	Permutation
A	B	AB
A	C	AC
B	A	BA
B	C	BC
C	A	CA
C	B	CB

🟰 Total Permutations = 6

 If you change the order, it’s a different permutation.

• AB ≠ BA
• AC ≠ CA

Types of Permutations with Examples

 1. Permutation Without Repetition

Formula: P(n, r) = n! / (n - r)!

Used when items are unique and not reused.

 

Example:

How many ways can you arrange 3 students out of 5?

P(5, 3) = 5! / (5 - 3)! = 120 / 2 = 60 ways

🟡 2. Permutation With Repetition

Formula: n^r

Used when items can be repeated.

 

Example:

How many 4-digit PINs can be formed using digits 0-9? 10^4 = 10,000 PINs

🟢 3. Permutation of All Items (n = r)

Formula: n!

Used when arranging all items.

 

Example:

How many ways can 4 books be arranged? 4! = 24 ways

🔵 4. Permutation of Repeated Items

Formula: n! / (p1! * p2! * ... * pk!) Used when some items repeat.

Example:

How many ways to arrange 'BALLOON'?

7 letters with L and O repeated: 7! / (2! * 2!) = 5040 / 4 = 1260 ways

🟣 5. Circular Permutations

Formula: (n - 1)!

Used when arranging items in a circle.

 

Example:

How many ways can 5 people sit at a round table? (5 - 1)! = 4! = 24 ways

⚪ 6. TOC-Based Example (Permutation of Input Strings)

Alphabet: {a, b, c}

Find all 2-symbol strings (repetition allowed): Strings: aa, ab, ac, ba, bb, bc, ca, cb, cc

Total: 3^2 = 9 permutations

 

🧠 Summary Table

Combination:

A combination is a selection of items from a larger pool where order does not matter.

Example: A farmer purchased 3 cows, 2 pigs, and 4 hens from a man who has 6 cows, 5 pigs, and 8 hens. Find the number m of choices that the farmer has.

The farmer can choose the cows in C (6, 3) ways, the pigs in C (5, 2) ways, and the hens in C (8, 4) ways. Thus the number m of choices follows:

1.3)Mathematical Induction

Mathematical induction is a proof technique used to prove that a statement is true for all natural numbers (or sometimes for strings of a certain length, etc.).

It works in two steps:

1. Base Case: Prove the statement is true for the initial value (usually n=0n = 0n=0 or n=1n = 1n=1).
2. Inductive Step: Assume it’s true for n=kn = kn=k, and then prove it's true for n=k+1n = k+1n=k+1.

In TOC, mathematical induction is used to prove properties of languages, grammars, automata, and recursive definitions.

✅ Common Applications in TOC:

Area	Use of Induction
Languages (L)	Proving all strings in a language satisfy certain properties
Recursive Definitions	Verifying correctness of a recursive or inductive definition
Derivation in Grammars (CFGs)	Proving that a grammar generates all strings in a pattern
Turing Machines	Proving a machine halts or accepts all inputs of length n
Regular Expressions	Showing equivalence between regex and finite automata

 

🔢 Example 1: Proving a String Property in a Language

 

 

 

 Example 2: Induction on Grammar Derivation

🧮 Example 3: Induction to Prove Regular Expression Length

Claim: A regular expression using only characters {a, b, +, ·, *} has at least nnn operators to generate nnn strings.

Induction can prove lower bounds or structural properties like this.

• Used to prove correctness and completeness of language definitions, automata behavior, and grammar derivations.
• Powerful tool for validating recursive or inductively defined structures in TOC.

 

 

 

1.4)PIGEON HOLE PRINCIPLE

If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is occupied by greater than one pigeon.

Example 5: Find the minimum number of students in a class to be sure that three of them are born in the same month.

Solution: 

Here n = 12 months are the Pigeonholes
                    And k + 1 = 3
                    K = 2

Example 6: Show that at least two people must have their birthday in the same month if 13 people are assembled in a room.

Solution: We assigned each person the month of the year on which he was born. Since there are 12 months in a year.

So, according to the pigeonhole principle, there must be at least two people assigned to the same month.

 

 

 

 

1.5)PRINCIPLE OF INCLUSION AND EXCLUSION

The Principle of Inclusion and Exclusion is a combinatorial method used to calculate the size of the union of multiple sets by correcting for overcounting the elements that appear in more than one set.

Where,

• ∣A∣ is the number of elements in set 𝐴.

• ∣B∣ is the number of element sin set B.

• ∣A∩B∣ is the number of elements in both set A and B.

Where,

·       ∣A∣ ,∣B∣, ∣C∣ are number of elements in the sets A,B and C respectively.

·       ∣A∩B∣,∣A∩C∣,∣B∩C∣ are the numbers of elements in the pairwise intersections of the sets.

·       ∣A∩B∩C∣ s the number of elements that are in all three sets.

 

 

 

 

 

Example 3:

Solved Examples

Problem 1: In a class of 100 students:

• 60 study Math.

• 45 study Science.

• 20 study both Math and Science.

How many students study either Math or Science?

Solution:

As we know, n(A⋃B) = n(A) + n(B) – n(A⋂B)

Given:

• n(A) = 60

• n(B) = 45

• n(A∩B) = 20

n(A⋃B) = n(A) + n(B) – n(A⋂B) = 60 + 45 - 20 = 85

Thus, 85 students study either Math or Science.

Problem 2 :The probability of getting at least one head is Problem: In a survey of 120 people:

• 80 people like tea.

• 70 people like coffee.

• 50 people like both tea and coffee.

How many people like either tea or coffee?

Solution:

As we know, n(A⋃B) = n(A) + n(B) – n(A⋂B)

Given:

• IAI = 80

• IBI = 70

• IA∩BI = 50

Thus, n(A⋃B) = 80 + 70 - 50 = 100

Thus, 100 people like either tea or coffee.

Problem 3: A company has 30 employees, 10 are assigned to Task A, 15 to Task B, and 5 are assigned to both. How many employees are assigned to at least one task?

Solution:

As we know, n(A⋃B) = n(A) + n(B) – n(A⋂B)

Given:

• IAI = 10 Task A

• IBI = 15 Task B

• IA∩BI = 5 Both tasks

Substitute the Values, We get

n(A⋃B) = 10 + 15 - 5 = 10

Thus, 20 employees are assigned to at least one task.

Problem 4 : In a survey of 200 people:

• 120 like pizza.

• 100 like burgers.

• 80 like tacos.

• 60 like both pizza and burgers.

• 40 like both burgers and tacos.

• 30 like both pizza and tacos.

• 20 like all three: pizza, burgers, and tacos.

How many people like at least one of these three foods?

Solution:

As we know, ∣AUBUC∣ = ∣A∣ + ∣B∣ + ∣C∣ - ∣A∩B∣ - ∣A∩C∣ - ∣B∩C∣ + ∣A∩B∩C∣

Given:

• ∣A∣ = 120 Pizza lovers

• ∣B∣ = 100 Burger lovers

• ∣C∣ = 80 Taco lovers

• ∣A∩B∣ = 60

• ∣A∩C∣ = 30

• ∣B∩C∣ = 40

• ∣A∩B∩C∣ = 20

Substituting in the formula, we get,

∣AUBUC∣ = 120 + 100 + 80 - 60 - 30 - 40 + 20 = 190

Thus, 190 people like at least one of the three foods.

Problem 5: In a university of 300 students:

• 150 students take Math.

• 120 students take Physics.

• 100 students take Chemistry.

• 80 students take both Math and Physics.

• 60 students take both Physics and Chemistry.

• 50 students take both Math and Chemistry.

• 30 students take all three subjects.

How many students are taking at least one subject?

Solution:

As we know, ∣AUBUC∣ = ∣A∣ + ∣B∣ + ∣C∣ - ∣A∩B∣ - ∣A∩C∣ - ∣B∩C∣ + ∣A∩B∩C∣

Given:

• ∣A∣ = 150 (Math),

• ∣B∣ = 120 (Physics),

• ∣C∣ = 100 (Chemistry),

• ∣A∩B∣ = 80

• ∣A∩C∣ = 60

• ∣B∩C∣ = 50

• ∣A∩B∩C∣ = 30

Substituting values, we get

∣AUBUC∣ = 150 + 120 + 100 - 80 - 60 - 50 + 30 = 210

Thus, 210 students are taking at least one subject.

Practice Problems

Problem 1: In a group of 200 people:

• 120 people like chocolate.

• 90 people like vanilla.

• 50 people like both chocolate and vanilla.

How many people like either chocolate or vanilla?

Problem 2: In a class of 100 students:

• 70 students play football.

• 60 students play basketball.

• 50 students play cricket.

• 30 students play both football and basketball.

• 25 students play both basketball and cricket.

• 20 students play both football and cricket.

• 15 students play all three sports.

How many students play at least one of these three sports?

Problem 3: Out of 150 attendees at an event:

• 80 attended Workshop A.

• 70 attended Workshop B.

• 40 attended both Workshop A and Workshop B.

How many people attended at least one workshop?

Problem 4: A card is drawn from a deck of 52 cards. What is the probability that it is:

• A heart,

• A face card (King, Queen, Jack),

• Or a red card (hearts or diamonds)?

There are 13 hearts, 12 face cards, and 26 red cards.

Note that:

• 3 face cards are also hearts,

• 6 face cards are red.

Problem 5: In a school of 300 students:

• 180 students are enrolled in Math.

• 150 students are enrolled in Science.

• 120 students are enrolled in English.

• 90 students are enrolled in both Math and Science.

• 80 students are enrolled in both Science and English.

• 70 students are enrolled in both Math and English.

• 50 students are enrolled in all three subjects.

How many students are enrolled in at least one subject?

Answer Key

1. 160 people like either chocolate or vanilla.

2. 120 students play at least one of these sports.

3. 110 people attended at least one workshop.

4. The probability is 8/13.

5. 260 students are enrolled in at least one subject.

 

1.6) GENERATING FUNCTION

A generating function is a formal power series used to represent sequences and solve combinatorial problems. It is especially useful for solving recurrence relations and counting strings in automata or grammar-related computations.

• It can be used to solve various kinds of Counting problems easily.

• It can be used to solve recurrence relations by translating the relation in terms of sequence to a problem about functions. 

• It can be used to prove combinatorial identities.

 

 

1.7) RECURRENCE RELATIONS

A recurrence relation defines a sequence where each term is based on previous terms using a mathematical rule.

In Theory of Computation (TOC), recurrence relations are used to:

• Count strings of a certain length
• Count derivations in grammars
• Analyze recursive patterns in automata
• Evaluate computational steps of machines

 STATEMENTS

In Theory of Computation (TOC) and Discrete Mathematics, a statement (also called a proposition) plays a crucial role in expressing logic, conditions, and rules used in automata, grammars, and computation models.

---

🔹 What is a Statement?

A statement is a declarative sentence that is either true or false, but not both at the same time.

It is the basic building block of logical reasoning.

---

🔸 Types of Statements

1. Simple Statement

• A statement that conveys a single idea.
• Example:
• "The number 5 is odd." ✅ (True)
• "Chennai is in India." ✅ (True)

·       These are basic logical statements which are either true or false, and cannot be broken further.

Statement	Truth Value	Explanation
"0 is a natural number."	✅ True	A fact in mathematics
"The set of all even numbers is finite."	❌ False	Even numbers are infinite
"A Turing Machine is a finite automaton."	❌ False	A TM is more powerful
"Chennai is in India."	✅ True	Geographical fact

2. Compound Statement

• A statement formed by combining two or more simple statements using logical connectives (AND, OR, NOT, etc.)
• Example:
• "The number is even and divisible by 2."
• p: "The number is even"
• q: "The number is divisible by 2"
• Compound statement: p ∧ q

---

🔸 Examples of Valid Statements

Statement	Type	Truth Value
"2 + 2 = 4"	Simple	True
"It is raining or it is sunny."	Compound	Depends
"If 5 is greater than 3, then 10 is even"	Conditional	True

These are formed by combining two or more simple statements using logical connectives.

Let:

• p: “The string contains only a’s”
• q: “The string is of even length”

Compound Statement	Symbolic Form	Truth Value	Explanation
“The string contains only a’s AND is of even length”	p ∧ q	Depends	True only if both p and q are true
“The string contains only a’s OR is of even length”	p ∨ q	Depends	True if at least one is true
“It is NOT the case that the string has only a’s”	¬p	Depends	Negation of p

---

🟪 3. Conditional Statements (Implication)

Used frequently in automata, grammars, and inference rules.

Statement	Symbolic Form	True when…
“If a string starts with ‘a’, then it is accepted.”	p → q	If p is true and q is true
“If a language is regular, then it can be represented by a DFA.”	p → q	True for regular languages
“If a grammar is context-free, it may not be regular.”	p → ¬q	Used to distinguish grammar classes

---

🟫 4. Bi-conditional Statements

Statements with ‘if and only if’ (iff) – used for equivalence in TOC.

Statement	Symbolic Form	Explanation
“A language is regular iff it can be accepted by a finite automaton.”	p ↔ q	Both directions must be true
“A DFA accepts a string iff there is a path from start to final state on that string.”	p ↔ q	Equivalence condition for DFA behavior

---

🟩 5. Quantified Statements (Used in Predicate Logic)

Quantifiers like ∀ (for all) and ∃ (there exists) are used in logic and formal language theory.

Statement	Symbolic Form	Explanation
“For all strings w ∈ L, w has even length.”	∀w ∈ L, Even(w)	Universal quantification
“There exists a string w such that w is a palindrome.”	∃w, Palindrome(w)	Existential quantification
“For every state q in DFA, there exists a transition for every input symbol.”	∀q ∈ Q, ∀a ∈ Σ, δ(q, a) ∈ Q	DFA completeness condition

---

🔁 6. TOC-Specific Statement Examples

Statement	True/False
“All regular languages can be accepted by some DFA.”	✅ True
“Every Turing Machine halts on all inputs.”	❌ False
“If a language is not regular, it can still be accepted by a PDA.”	✅ True
“A finite automaton can accept infinite languages.”	✅ True
“There exists a language that is not recognized by any Turing Machine.”	✅ True
“If a string contains equal number of a’s and b’s, it belongs to the language L.”	Depends

---

Type	Example
Simple	"Language L is regular."
Compound	"L is regular AND accepted by a DFA"
Conditional	"If string has even length, then it is accepted"
Bi-conditional	"L is regular iff accepted by a DFA"
Quantified	"∀w ∈ L, length(w) is even"

❌ Not Statements (Why?)

These do not qualify as statements in logic because they are not clearly true or false:

Sentence	Reason
"What time is it?"	It’s a question
"Go to the store."	It’s a command
"x + 3 = 5"	Depends on value of x

To become a statement, variables must be defined.
✅ Example: "x + 3 = 5, where x = 2" → Now it’s a true statement.

---

🔹 Sample TOC-Related Statement

Example:

"If a string ends with ‘01’, then it belongs to language L."

• This is a conditional statement.
• Can be expressed logically as:
• p: "String ends with 01"
• q: "String ∈ L"
• Statement: p → q

---

Concept	Description	Example
Statement	Sentence that is clearly true or false	"2 is even" → True
Simple	One idea	"Computer is on"
Compound	Multiple ideas with logic (AND, OR, NOT)	"It is hot AND sunny"
Use in TOC	For transitions, rules, and grammar formulation	"If a is followed by b, accept"

 

 

 

CONNECTIVES

🔹 What are Connectives?

Connectives (also called logical operators) are used to combine or modify statements (propositions) to form compound logical expressions.
They help represent conditions, rules, and decisions in automata, grammars, and formal logic.

---

🔸 Types of Logical Connectives

Connective	Symbol	Meaning
AND	∧	True if both statements are true
OR	∨	True if at least one is true
NOT	¬	Reverses the truth value
IMPLIES	→	“If p, then q”
BICONDITIONAL	↔	“p if and only if q” (iff)

---

🧩 Truth Table Summary

p	q	¬p	p ∧ q	p ∨ q	p → q	p ↔ q
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

---

🔹 Examples of Connectives in TOC

---

✅ 1. AND ( ∧ )

Meaning: The result is true only if both conditions are true.

Example:

• Let:
• p: “The input string ends in ‘0’”
• q: “The input length is even”
• p ∧ q:
  “The input string ends in ‘0’ and the input length is even”

TOC Use Case:

• A state transition in a finite automaton can depend on two conditions being met simultaneously.

---

✅ 2. OR ( ∨ )

Meaning: True if at least one of the conditions is true.

Example:

• p: “The string contains ‘ab’”
• q: “The string contains ‘ba’”
• p ∨ q:
  “The string contains ‘ab’ or ‘ba’”

TOC Use Case:

• A regular expression like (ab)|(ba) represents a language accepting either pattern.

---

✅ 3. NOT ( ¬ )

Meaning: Reverses the truth value of a statement.

Example:

• p: “The string is accepted by the DFA”
• ¬p:
  “The string is not accepted by the DFA”

TOC Use Case:

• Used in complement of languages:
  If L is a regular language, then its complement ¬L is also regular.

---

✅ 4. IMPLICATION ( → )

Meaning: “If p is true, then q must also be true.”
Only false when p is true and q is false.

Example:

• p: “The input starts with ‘a’”
• q: “The machine moves to state q1”
• p → q:
  “If the input starts with ‘a’, then move to state q1”

TOC Use Case:

• In inference rules for grammars or proof systems:
  If condition A holds, then rule B applies.

---

✅ 5. BICONDITIONAL ( ↔ )

Meaning: “p is true if and only if q is true.”
Both must be either true or false.

Example:

• p: “A string ends in ‘00’”
• q: “It is accepted by a DFA for even 0s”
• p ↔ q:
  “The string ends in ‘00’ iff it is accepted by the machine”

TOC Use Case:

• Used to prove equivalence between machines and languages (e.g., DFA ≡ NFA)

---

🛠️ Real-World TOC Examples Using Connectives

---

📌 Example 1: Regular Language Rule

Statement:
“If a string starts and ends with the same symbol, it is in language L.”

Let:

• p: "String starts and ends with same symbol"
• q: "String ∈ L"

Logical Form:
p → q

---

📌 Example 2: Pushdown Automaton Rule

Statement:
“If top of stack is A and input is ‘b’, then pop A and move to q2.”

Let:

• p: "Top of stack is A"
• q: "Input is ‘b’"
• r: "Move to q2"

Logical Form:
(p ∧ q) → r

---

📌 Example 3: Context-Free Grammar

Statement:
“A non-terminal A can derive ‘aa’ or ‘bb’.”

Let:

• p: A → aa
• q: A → bb

Logical Form:
p ∨ q

---

📌 Example 4: Closure Property

Statement:
“If L1 and L2 are regular, then L1 ∪ L2 is regular.”

Let:

• p: "L1 and L2 are regular"
• q: "L1 ∪ L2 is regular"

Logical Form:
p → q

---

✅ Summary Table of Use

Connective	Used For...	Example
∧ (AND)	Both conditions true	"Starts with a AND ends with b"
∨ (OR)	One of multiple conditions	"Contains ab OR ba"
¬ (NOT)	Reversal/negation	"NOT accepted by the machine"
→ (Implies)	Rules and conditional transitions	"If starts with a, go to q1"
↔ (IFF)	Equivalence	"String ∈ L ↔ machine accepts it"

 

 

NORMAL FORMS

🟨 Definition: Normal Forms in TOC

·       In Theory of Computation, a normal form is a standardized structure or format for writing logical expressions or grammar production rules.

·       Normal forms help simplify, analyze, and apply algorithms to grammars or logical formulas.

---

🧠 Two Main Areas in TOC Where Normal Forms Are Used:

A. Logical Normal Forms (used in propositional logic)

B. Grammar Normal Forms (used in context-free grammars)

---

🔷 A. Normal Forms in Logic

These are ways to rewrite logical formulas/statements in a structured format using logical connectives (∧, ∨, ¬, →, ↔).

---

✅ 1. Conjunctive Normal Form (CNF)

Definition: A formula is in CNF if it is a conjunction (AND) of one or more clauses, where each clause is a disjunction (OR) of literals.

📌 Structure:

(p ∨ q) ∧ (¬p ∨ r)

✅ Examples:

1. Convert p → q to CNF:
• p → q ≡ ¬p ∨ q → Already in CNF
2. Convert ¬(p ∧ q) to CNF:
• Apply DeMorgan’s Law → ¬p ∨ ¬q → CNF

---

✅ 2. Disjunctive Normal Form (DNF)

Definition: A formula is in DNF if it is a disjunction (OR) of one or more conjunctions (AND) of literals.

📌 Structure:

(p ∧ q) ∨ (¬r ∧ s)

✅ Examples:

1. Convert ¬(p ∨ q) to DNF:
• Apply DeMorgan: ¬p ∧ ¬q → Already in DNF
2. From truth table:
• If the statement is true when p=T, q=F:
  → Corresponding term: p ∧ ¬q

---

🔷 B. Normal Forms in Context-Free Grammars (CFGs)

These are used to standardize grammar rules to simplify parsing and proofs.

---

✅ 1. Chomsky Normal Form (CNF)

Definition: A CFG is in Chomsky Normal Form if every production is of the form:

• A → BC (two non-terminals)
• A → a (a single terminal)
• Optionally: S → ε (if ε is in the language)

---

✅ Example 1:

Original grammar:

S → aSb | ε

Convert to CNF:

Introduce:

• A → a
• B → b

Then rewrite:

S → A S B 

S → ε

Now it's in CNF:

S → ASB 

S → ε 

A → a 

B → b

---

✅ Example 2:

A → B 

B → b

Remove unit production (A → B) by replacing it:

A → b 

B → b

---

✅ 2. Greibach Normal Form (GNF)

Definition: A CFG is in GNF if every production is of the form:

• A → aα
  where a is a terminal and α is a (possibly empty) string of non-terminals.

---

✅ Example:

S → aA 

A → bS 

A → a

All productions start with a terminal, followed by non-terminals or nothing.
✅ This is already in GNF.

---

🧾 Summary Table

Type	Area	Definition	Example
CNF (Logic)	Logic	AND of ORs	(p ∨ q) ∧ (¬r ∨ s)
DNF (Logic)	Logic	OR of ANDs	(p ∧ q) ∨ (¬p ∧ r)
CNF (CFG)	Grammar	A → BC or A → a	S → ASB, A → a, B → b
GNF (CFG)	Grammar	A → aX (starts with terminal)	A → aB, A → b

 

Predicate Calculus

Predicate Calculus, also called First-Order Logic (FOL), is a formal system used to represent and reason about statements involving:

• Variables (like x, y, z)
• Quantifiers (like ∀, ∃)
• Predicates (like Student(x), Even(x))

It extends propositional logic by allowing us to talk about objects and their properties.

---

🟨 Why Predicate Calculus in TOC?

Predicate calculus is used in TOC for:

• Defining formal languages
• Expressing computational properties
• Designing logical inference systems
• Writing rules for automata and grammars

---

🧠 Basic Concepts in Predicate Calculus

Concept	Symbol / Form	Meaning
Predicate	P(x), Q(x, y)	Statement about variable(s)
Universal Quantifier	∀x P(x)	"For all x, P(x) is true"
Existential Quantifier	∃x P(x)	"There exists x such that P(x)"
Logical Connectives	∧, ∨, ¬, →, ↔	Same as in propositional logic

---

✅ Examples of Predicate Statements

🔸 1. Predicate:

Let:

• P(x): "x is a prime number"

Then:

• P(3): "3 is a prime number" → ✅ True
• P(4): "4 is a prime number" → ❌ False

---

🔸 2. Universal Quantifier (∀):

Statement:

• ∀x ∈ ℕ, P(x): “All natural numbers are prime” → ❌ False
• ∀x ∈ ℕ, x ≥ 0: “All natural numbers are non-negative” → ✅ True

---

🔸 3. Existential Quantifier (∃):

Statement:

• ∃x ∈ ℕ, P(x): “There exists a prime number” → ✅ True
• ∃x ∈ ℕ, x < 0: “There exists a negative natural number” → ❌ False

---

🔁 Combining Predicates with Connectives

Let:

• P(x): “x is even”
• Q(x): “x is divisible by 2”

Then:

• P(x) ∧ Q(x) → "x is even AND divisible by 2"
• P(x) ∨ Q(x) → "x is even OR divisible by 2"
• ¬P(x) → "x is NOT even"
• P(x) → Q(x) → "If x is even, then x is divisible by 2"

---

💡 More Examples

📌 Example 1:

Statement: “All strings over {a, b} contain at least one ‘a’.”

Let:

• S(x): “x contains at least one ‘a’”

Then:

• ∀x ∈ Σ*, S(x)

---

📌 Example 2:

Statement: “There exists a string of even length.”

Let:

• E(x): “x is a string of even length”

Then:

• ∃x ∈ Σ*, E(x)

---

📌 Example 3:

Statement: “If a machine accepts a string, then it belongs to language L.”

Let:

• A(x): “Machine accepts x”
• L(x): “x ∈ L”

Then:

• ∀x (A(x) → L(x))

---

📌 Example 4:

Statement: “All even numbers greater than 2 are the sum of two primes.” (Goldbach's conjecture)

Let:

• E(x): x is even and > 2
• P(x): x is prime
• ∀x (E(x) → ∃a ∃b (P(a) ∧ P(b) ∧ x = a + b))

---

🧾 Summary Table

Form	Meaning
P(x)	Predicate statement
∀x P(x)	For all x, P(x) is true
∃x P(x)	There exists x such that P(x) is true
¬P(x)	P(x) is not true
P(x) ∧ Q(x)	Both P(x) and Q(x) are true
P(x) → Q(x)	If P(x), then Q(x)

---

🔷 Use of Predicate Calculus in TOC

Application	Example
Formal language rules	∀w ∈ Σ*, if w ends in '01' then w ∈ L
Automata acceptance	∃q ∈ F, δ*(q0, w) = q
Turing machine logic	∃x, TM halts on x
Grammar derivations	∀S ∈ G, ∃w ∈ Σ*, S ⇒* w

Inference In Toc

Inference in TOC refers to the process of logically deriving new statements (conclusions) from a given set of premises or rules, using formal logic systems such as propositional logic or predicate logic.

It is a core part of:

• Formal proof systems
• Logic-based computation
• Syntax and semantics of languages
• Automated theorem proving

---

🧠 Why Inference Matters in TOC?

In TOC, inference allows us to:

• Prove whether a string belongs to a language
• Deduce consequences from grammar rules
• Check the validity of logical formulas
• Simulate derivations in grammars or automata

---

🛠️ Types of Inference Rules (Logical Inference)

Here are the most common inference rules used in TOC:

Inference Rule	Form	Meaning
Modus Ponens	From: p → q, p ⇒ infer q	If p implies q and p is true, then q is true
Modus Tollens	From: p → q, ¬q ⇒ infer ¬p	If p implies q, and q is false, then p is false
Hypothetical Syllogism	From: p → q, q → r ⇒ p → r	Chain implications
Disjunctive Syllogism	From: p ∨ q, ¬p ⇒ infer q	One must be true; eliminate one
Conjunction	From: p, q ⇒ infer p ∧ q	Combine two truths
Simplification	From: p ∧ q ⇒ infer p or q	Extract part of a compound statement

---

✅ Examples of Inference

---

📌 Example 1: Modus Ponens

Given:

• p: “It is raining”
• q: “The ground will be wet”
• Rule: p → q
• Fact: p is true

Inference:
Since it is raining, and rain causes wet ground,
✅ Therefore: q (The ground is wet)

---

📌 Example 2: Grammar Derivation (Inference in CFG)

Given Grammar G:

S → aA 

A → b

We want to infer:
Does ab ∈ L(G)?

Inference:

• S ⇒ aA ⇒ ab
  ✅ Yes, by inference from the rules, ab is in the language.

---

📌 Example 3: Turing Machine Acceptance

Given:

• δ(q0, 0) = q1
• δ(q1, 1) = qf (final state)

String = "01"

Inference:
Start at q0, input 0 → q1
Then input 1 → qf
✅ Hence, "01" is accepted by inference from transition rules.

---

📌 Example 4: Predicate Logic

Let:

• P(x): x is an even number
• Q(x): x is divisible by 2
• ∀x (P(x) → Q(x))
• P(6)

Inference:
Since P(6) is true and P(x) → Q(x) holds,
✅ Therefore: Q(6) is true

---

🔁 Inference in Formal Proof Systems

In TOC, we use inference to prove:

• Whether a formula is valid (always true)
• Whether a string belongs to a language
• Whether a grammar can derive a certain string

Example:

If ⊢ φ (phi), we say "φ is derivable (provable)" using inference rules.

---

🧾 Summary Table

Use Case	Inference Example
Logic	From p → q, and p, infer q
Grammar Derivation	From S → aA, A → b, infer S ⇒ ab
Language Membership	Show w ∈ L using grammar rules
Turing Machine Acceptance	Apply transition rules to reach final state

Inference is the foundation of logical reasoning in TOC.
It is essential in:

• Proof writing
• Language design
• Automata simulation
• Verifying computation models

THEORY FOR STATEMENT CALCULUS AND PREDICATE CALCULUS

🟩 1. Statement Calculus (Propositional Logic)

Deals with simple statements and how they combine using logical connectives.

---

✅ Example 1: p ∧ q

Meaning: "It is raining AND the road is wet"

• This is true only when both p and q are true.
• Useful when both conditions must happen for a result.

---

✅ Example 2: p ∨ q

Meaning: "It is raining OR the road is wet"

• This is true if either it is raining, or the road is wet, or both.
• Used when at least one condition is enough.

---

✅ Example 3: p → q

Meaning: "If it is raining, then the road is wet"

• A conditional statement.
• If p is true and q is false, this implication is false.
• Otherwise, it’s true.

---

✅ Example 4: ¬p

Meaning: "It is NOT raining"

• This simply negates the statement p.
• If p is true, ¬p is false and vice versa.

---

✅ Example 5: (p ∧ q) → r

Meaning: "If it is raining AND the road is wet, then the ground is slippery"

• This means that only when both p and q are true, r must be true.
• Used to express combined cause-and-effect.

---

✅ Example 6: p ↔ q

Meaning: "It is raining if and only if the road is wet"

• This is true when both p and q are either true or false together.
• Used for equivalent conditions.

---

🟨 2. Predicate Calculus (First-Order Logic)

Deals with variables, quantifiers, and properties of objects.

---

Let’s define:

• P(x): "x is even"
• Q(x): "x is divisible by 2"
• L(x): "x belongs to language L"
• Accept(x): "x is accepted by a machine"

---

✅ Example 1: ∀x (P(x) → Q(x))

Meaning: "For all x, if x is even, then x is divisible by 2"

• This says every even number must also be divisible by 2.
• It's universally quantified — applies to all x in the domain.

---

✅ Example 2: ∃x P(x)

Meaning: "There exists an x such that x is even"

• Means at least one number exists that is even.
• True if x = 2, 4, etc.

---

✅ Example 3: ∀x (L(x) → Accept(x))

Meaning: "All strings in language L are accepted"

• For every string x, if x is in the language L, then the machine must accept it.
• Used in formal language definitions.

---

✅ Example 4: ∃x (¬P(x))

Meaning: "There exists an x such that x is not even"

• At least one x is not even (like 1, 3, 5).
• Shows exceptions.

---

✅ Example 5: ∀x ∃y (x < y)

Meaning: "For every x, there exists a y such that x is less than y"

• Always true in natural numbers — for any x, we can pick y = x+1.
• Shows infinite growth.

---

✅ Example 6: ∃x (P(x) ∧ Q(x))

Meaning: "There exists an x such that x is even and divisible by 2"

• Like x = 4 → it's even and divisible by 2 → ✅ True
• Used to show existence of items with multiple properties.

---

🧾 Recap Table

Logic Type	Example	What It Means
Propositional	p ∧ q	Both p and q are true
Propositional	p → q	If p is true, then q must be true
Predicate	∀x (P(x) → Q(x))	All even numbers are divisible by 2
Predicate	∃x (¬P(x))	At least one number is not even
Predicate	∀x ∃y (x < y)	Every number has a greater number