
- Automata Theory - Applications
- Automata Terminology
- Basics of String in Automata
- Set Theory for Automata
- Finite Sets and Infinite Sets
- Algebraic Operations on Sets
- Relations Sets in Automata Theory
- Graph and Tree in Automata Theory
- Transition Table in Automata
- What is Queue Automata?
- Compound Finite Automata
- Complementation Process in DFA
- Closure Properties in Automata
- Concatenation Process in DFA
- Language and Grammars
- Language and Grammar
- Grammars in Theory of Computation
- Language Generated by a Grammar
- Chomsky Classification of Grammars
- Context-Sensitive Languages
- Finite Automata
- What is Finite Automata?
- Finite Automata Types
- Applications of Finite Automata
- Limitations of Finite Automata
- Two-way Deterministic Finite Automata
- Deterministic Finite Automaton (DFA)
- Non-deterministic Finite Automaton (NFA)
- NDFA to DFA Conversion
- Equivalence of NFA and DFA
- Dead State in Finite Automata
- Minimization of DFA
- Automata Moore Machine
- Automata Mealy Machine
- Moore vs Mealy Machines
- Moore to Mealy Machine
- Mealy to Moore Machine
- Myhill–Nerode Theorem
- Mealy Machine for 1’s Complement
- Finite Automata Exercises
- Complement of DFA
- Regular Expressions
- Regular Expression in Automata
- Regular Expression Identities
- Applications of Regular Expression
- Regular Expressions vs Regular Grammar
- Kleene Closure in Automata
- Arden’s Theorem in Automata
- Convert Regular Expression to Finite Automata
- Conversion of Regular Expression to DFA
- Equivalence of Two Finite Automata
- Equivalence of Two Regular Expressions
- Convert Regular Expression to Regular Grammar
- Convert Regular Grammar to Finite Automata
- Pumping Lemma in Theory of Computation
- Pumping Lemma for Regular Grammar
- Pumping Lemma for Regular Expression
- Pumping Lemma for Regular Languages
- Applications of Pumping Lemma
- Closure Properties of Regular Set
- Closure Properties of Regular Language
- Decision Problems for Regular Languages
- Decision Problems for Automata and Grammars
- Conversion of Epsilon-NFA to DFA
- Regular Sets in Theory of Computation
- Context-Free Grammars
- Context-Free Grammars (CFG)
- Derivation Tree
- Parse Tree
- Ambiguity in Context-Free Grammar
- CFG vs Regular Grammar
- Applications of Context-Free Grammar
- Left Recursion and Left Factoring
- Closure Properties of Context Free Languages
- Simplifying Context Free Grammars
- Removal of Useless Symbols in CFG
- Removal Unit Production in CFG
- Removal of Null Productions in CFG
- Linear Grammar
- Chomsky Normal Form (CNF)
- Greibach Normal Form (GNF)
- Pumping Lemma for Context-Free Grammars
- Decision Problems of CFG
- Pushdown Automata
- Pushdown Automata (PDA)
- Pushdown Automata Acceptance
- Deterministic Pushdown Automata
- Non-deterministic Pushdown Automata
- Construction of PDA from CFG
- CFG Equivalent to PDA Conversion
- Pushdown Automata Graphical Notation
- Pushdown Automata and Parsing
- Two-stack Pushdown Automata
- Turing Machines
- Basics of Turing Machine (TM)
- Representation of Turing Machine
- Examples of Turing Machine
- Turing Machine Accepted Languages
- Variations of Turing Machine
- Multi-tape Turing Machine
- Multi-head Turing Machine
- Multitrack Turing Machine
- Non-Deterministic Turing Machine
- Semi-Infinite Tape Turing Machine
- K-dimensional Turing Machine
- Enumerator Turing Machine
- Universal Turing Machine
- Restricted Turing Machine
- Convert Regular Expression to Turing Machine
- Two-stack PDA and Turing Machine
- Turing Machine as Integer Function
- Post–Turing Machine
- Turing Machine for Addition
- Turing Machine for Copying Data
- Turing Machine as Comparator
- Turing Machine for Multiplication
- Turing Machine for Subtraction
- Modifications to Standard Turing Machine
- Linear-Bounded Automata (LBA)
- Church's Thesis for Turing Machine
- Recursively Enumerable Language
- Computability & Undecidability
- Turing Language Decidability
- Undecidable Languages
- Turing Machine and Grammar
- Kuroda Normal Form
- Converting Grammar to Kuroda Normal Form
- Decidability
- Undecidability
- Reducibility
- Halting Problem
- Turing Machine Halting Problem
- Rice's Theorem in Theory of Computation
- Post’s Correspondence Problem (PCP)
- Types of Functions
- Recursive Functions
- Injective Functions
- Surjective Function
- Bijective Function
- Partial Recursive Function
- Total Recursive Function
- Primitive Recursive Function
- μ Recursive Function
- Ackermann’s Function
- Russell’s Paradox
- Gödel Numbering
- Recursive Enumerations
- Kleene's Theorem
- Kleene's Recursion Theorem
- Advanced Concepts
- Matrix Grammars
- Probabilistic Finite Automata
- Cellular Automata
- Reduction of CFG
- Reduction Theorem
- Regular expression to ∈-NFA
- Quotient Operation
- Parikh’s Theorem
- Ladner’s Theorem
Injective Functions in Automata Theory
Read this chapter to understand the concept of one-to-one functions in automata theory. One-to-one functions are also known as injective functions. These functions play an important role in Set Theory too. We will see their definitions with examples and their properties for a better understanding.
One-to-One (Injective) Function
A one-to-one function, also called an injective function, is a function that maps elements from one set, say Set A, to another set, Set B, in such a way that no two elements in Set A map to the same element in Set B. This means that each element of Set A has a unique image in Set B.

Here, A contains {1, 2, 3} and B contains {a, b, c} the function is like the above figure and it is one to one function.
Let us see another example which is not one-to-one.
- Set A contains three elements: {1, 2, 3}.
- Set B contains two elements: {A, B}.
Let's map the elements from Set A to Set B −

This is not a one-to-one function because both 2 and 3 map to B. In a one-to-one function, each element of Set A must map to a unique element in Set B. Thus, if: 1 maps to A, 2 maps to B, 3 maps to C, this function would be injective because each element of Set A has a distinct image in Set B.
Condition for Injectivity
For a function to be injective, it must satisfy the following condition −
- For any two elements a and b in Set A, if a ≠ b, then f(a) ≠ f(b) − This means that if two elements in Set A are different, their images in Set B must also be different.
- Number of elements in set A must be less than on equal to the number of elements in set B − This will also be injective.

Number of Injective Functions
The number of possible injective functions depends on the sizes of Set A and Set B. Let's consider an example −
- Set A has 3 elements: {1, 2, 3}
- Set B has 4 elements: {A, B, C, D}
To find the total number of one-to-one functions from Set A to Set B, we use the formula for permutations −
- The first element in Set A has 4 possible choices in Set B.
- Once the first element is mapped, the second element has 3 choices.
- The third element then has 2 choices.
So, the total number of injective functions is: 4 × 3 × 2 = 24
This means there are 24 possible injective functions from Set A to Set B when Set A has 3 elements and Set B has 4 elements.
General Formula for Injective Functions
If Set A has m elements and Set B has n elements, the number of injective functions is given by −
$$\mathrm{n \: \times \: (n \:-\: 1) \: \times \: (n \:-\: 2) \: \times \: \dotso \: \times \: (n \:-\: m \:+\: 1)}$$
This is denoted as nPm, where P stands for permutations.
Special Case: When Sets A and B Are Equal
If the number of elements in Set A is equal to the number of elements in Set B (m = n), the formula simplifies to nPn, which is simply n! (n factorial).
Confusion with Many-to-One Functions
It is common to confuse one-to-one (injective) functions with many-to-one functions. In a many to one function, multiple elements in Set A can map to the same element in Set B. For example, if both 1 and 2 in Set A map to a in Set B, it is a many-to-one function.

Not a Function
In the following example, there is a scenario where A has some element which is not mapped to B. This is not a function either, so there is no need to check one-to-one or anything else.

Real-World Applications of Injective Functions
Injective functions are not just theoretical; they have practical applications in computer science and other fields.
- Cryptography − In cryptography, injective functions are used in the design of encryption algorithms where each plaintext must map to a unique ciphertext to ensure secure communication.
- Database Management − In databases, injective functions help maintain data integrity by ensuring that unique keys map to unique records, preventing data duplication.
Conclusion
In this chapter, we covered one-to-one or injective functions, their definition, properties, and applications. We used examples to demonstrate what makes a function injective and explored the importance of injective functions in other real-world applications.