Theory of Computation - Practical Implementations

This repository contains practical implementations for the Theory of Computation (TOC) course, part of the B.Sc. (Hons.) Computer Science curriculum, 5th Semester, Delhi University.

📚 About

This collection includes C++ implementations of various computational models including:

• Finite Automata (FA)
• Pushdown Automata (PDA)
• Turing Machines (TM)

Each practical demonstrates fundamental concepts in automata theory and formal languages through working simulations.

📋 List of Practicals

1. Three Consecutive 1's (FA)

File: P1.cpp

Design a Finite Automata that accepts all strings over Σ={0, 1} having three consecutive 1's as a substring.

Example:

• Input: 111 → Accepted
• Input: 0111 → Accepted
• Input: 1101 → Rejected

---

2. Exactly Two or Three 1's (FA)

File: P2.cpp

Design a Finite Automata that accepts strings over Σ={0, 1} having either exactly two 1's or exactly three 1's, not more nor less.

Example:

• Input: 110 → Accepted (two 1's)
• Input: 1011 → Rejected (three 1's but needs to be exactly 2 or 3)

---

3. First Two Same as Last Two (FA)

File: P3.cpp

Design a Finite Automata that accepts language L1 over Σ={a, b}, comprising of all strings (of length 4 or more) having first two characters same as the last two.

Example:

• Input: abab → Accepted
• Input: aabbaa → Accepted
• Input: abba → Rejected

---

4. Language a(a+b)*b (FA)

File: P4.cpp

Design a Finite Automata that accepts language L2 over Σ={a, b} where L2 = a(a+b)*b.

Example:

• Input: ab → Accepted
• Input: aab → Accepted
• Input: ba → Rejected

---

5. EVEN-EVEN Language (FA)

File: P5.cpp

Design a Finite Automata that accepts the EVEN-EVEN language over Σ={a, b} (strings with even number of a's and even number of b's).

Example:

• Input: `` (empty string) → Accepted
• Input: aabb → Accepted
• Input: aba → Rejected

---

6. Set Operations on Languages (FA)

File: P6.cpp

Write a program to simulate an FA that performs:

• a. Union of languages L1 and L2
• b. Intersection of languages L1 and L2
• c. Concatenation L1L2

Example:

• L1 = {a, ab}
• L2 = {b, ab}
• Union: {a, ab, b}
• Intersection: {ab}
• Concatenation: {ab, aab, abb, abab}

---

7. Language a^n b^n (PDA)

File: P7.cpp

Design a Pushdown Automata that accepts the language {a^n b^n | n > 0, Σ={a, b}}.

Example:

• Input: ab → Accepted
• Input: aabb → Accepted
• Input: aaab → Rejected

---

8. Palindrome with Middle Marker (PDA)

File: P8.cpp

Design a Pushdown Automata that accepts the language {wXw^r | w is any string over Σ={a, b} and w^r is reverse of that string and X is a special symbol}.

Example:

• Input: aXa → Accepted
• Input: abXba → Accepted
• Input: abXab → Rejected

---

9. Language a^n b^n c^n (Turing Machine)

File: P9.cpp

Design and simulate a Turing Machine that accepts the language a^n b^n c^n where n > 0.

Example:

• Input: abc → Accepted
• Input: aabbcc → Accepted
• Input: aabbc → Rejected

---

10. Binary Increment (Turing Machine)

File: P10.cpp

Design and simulate a Turing Machine which increments a given binary number by 1.

Example:

• Input: 1010 → Output: 1011
• Input: 1111 → Output: 10000
• Input: 0 → Output: 1

---

🔧 Prerequisites

• C++ Compiler (g++, clang, or any C++11 compatible compiler)
• Basic understanding of:
  • Automata theory
  • Finite state machines
  • Regular languages
  • Context-free languages

💻 Compilation and Execution

Compiling a Program

Using g++:

g++ P1.cpp -o P1

Using clang++:

clang++ P1.cpp -o P1

Running a Program

On Linux/macOS:

./P1

On Windows:

P1.exe

Quick Compile and Run

You can combine compilation and execution:

g++ P1.cpp && ./a.out

📖 Usage Examples

Example 1: Testing Three Consecutive 1's (P1)

$ g++ P1.cpp -o P1
$ ./P1
Enter string: 0111
Read 0 -->String 1
Read 1---> String 2
Read 1---> String 3
String accepted

Example 2: Testing EVEN-EVEN Language (P5)

$ g++ P5.cpp -o P5
$ ./P5
Enter string: aabb
Read a ---> q1
Read a ---> q0
Read b ---> q2
Read b ---> q0
String accepted (even a's, even b's)

Example 3: Testing a^n b^n (P7)

$ g++ P7.cpp -o P7
$ ./P7
Enter a string of a's followed by b's (e.g., aabb): aabb
String is accepted by the PDA (in the language a^n b^n, n>0).

Example 4: Binary Increment (P10)

$ g++ P10.cpp -o P10
$ ./P10
Enter binary number: 1111
Result: 10000

📁 Repository Structure

.
├── P1.cpp          # FA: Three consecutive 1's
├── P2.cpp          # FA: Exactly two or three 1's
├── P3.cpp          # FA: First two same as last two
├── P4.cpp          # FA: Language a(a+b)*b
├── P5.cpp          # FA: EVEN-EVEN language
├── P6.cpp          # FA: Set operations (union, intersection, concatenation)
├── P7.cpp          # PDA: a^n b^n language
├── P8.cpp          # PDA: Palindrome with middle marker
├── P9.cpp          # TM: a^n b^n c^n language
├── P10.cpp         # TM: Binary increment
├── LICENSE         # Apache License 2.0
└── README.md       # This file

🎓 Learning Outcomes

By working through these practicals, students will:

• Understand the design and implementation of Finite Automata
• Learn to simulate DFA and NFA
• Implement Pushdown Automata for context-free languages
• Build basic Turing Machine simulations
• Gain practical experience with formal language theory
• Develop skills in computational problem-solving

📝 Notes

• All programs are written in C++ and follow standard conventions
• Programs use interactive input/output for testing
• Each file contains comments describing the problem statement
• State transitions are implemented using recursive function calls
• Some programs provide detailed trace output showing state transitions

🤝 Contributing

This is an educational repository for Delhi University students. If you find any bugs or have suggestions for improvements:

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Submit a pull request

📄 License

This project is licensed under the Apache License 2.0 - see the LICENSE file for details.

👥 Author

Ananya Srivastava

Created for B.Sc. (Hons.) Computer Science students, Delhi University

---

Course: Theory of Computation
Semester: 5th
University: Delhi University
Program: B.Sc. (Hons.) Computer Science