A Laboratory Manual for

Theory Of Computation
(3164203)

B.E. Semester 6
(Artificial Intelligence & Machine Learning)

Enrolment No: 230280152068

Name: Sonara Prince Jagdishkumar

L.D. College of Engineering, Ahmedabad

Directorate of Technical Education, Gandhinagar,
Gujarat
Theory of Computation (3164203) Enrollment no:230280152068

2
Theory of Computation (3164203) Enrollment no:230280152068

LD College of Engineering, Ahmedabad

Department of Computer Engineering

CERTIFICATE

This is to certify that Mr. Sonra Prince Jagdishkumar Enrollment No.

230280152068 of B.E. Semester - VI from Artificial Intelligence and Machine
Learning of this Institute (GTU Code: 028) has satisfactorily completed the Practical
/ Assignment work for the subject Theory Of Computation(3164203) for the
academic year 2025-2026.

Place: ____________________

Date: _____________________

Signature of Course Faculty Head of Department

3
Theory of Computation (3164203) Enrollment no:230280152068

4
Theory of Computation (3164203) Enrollment no:230280152068

DTE’s Vision

• To provide globally competitive technical education

• Remove geographical imbalances and inconsistencies
• Develop student friendly resources with a special focus on girls’ education and support to weaker
sections
• Develop programs relevant to industry and create a vibrant pool of technical professionals

Institute’s Vision

• To contribute for sustainable development of nation through achieving excellence in technical

education and research while facilitating transformation of students into responsible citizens and
competent professionals.

Institute’s Mission

• To impart affordable and quality education in order to meet the needs of industries and achieve
excellence in teaching-learning process.
• To create a conducive research ambience that drives innovation and nurtures scholars and
outstanding professionals.
• To collaborate with other academic & research institutes as well as industries in order to strengthen
education and multidisciplinary research.
• To promote equitable and harmonious growth of students, academicians, staff, society and
industries, thereby becoming a centre of excellence in technical education.
• To practice and encourage high standards of professional ethics, transparency and accountability.

Department’s Vision

• To achieve academic excellence in Computer Engineering by providing value based education.

Department’s Mission

• To produce graduates according to the needs of industry, government, society and scientific
community. To develop partnership with industries, research and development organizations and
government sectors for continuous improvement of faculties and students.
• To motivate students for participating in reputed conferences, workshops, seminars and technical
events to make them technocrats and entrepreneurs.
• To enhance the ability of students to address the real-life issues by applying technical expertise,
human values and professional ethics.
• To inculcate habit of using free and open-source software, latest technology and soft skills so that
they become competent professionals.
• To encourage faculty members to upgrade their skills and qualification through training and higher
studies at reputed universities

5
Theory of Computation (3164203) Enrollment no:230280152068

6
 Theory of Computation (3164203) Enrollment no:230280152068

INDEX
(Progressive Assessment Sheet)

Asses Sign of
Date of Date of sment
Sr. Objective(s) of Experiment Page Teach Rem
Perfor Submis Mark
No. No. er arks
mance sion s

Implement a Python script to check if a

1 given string matches a regular expression.

Implement a DFA that recognizes binary

2 strings divisible by 3.
Convert a given NFA to DFA.
3

Implement a Python program that

4 minimizes a given Deterministic Finite
Automaton (DFA).

Implement a Python program to check if a

5 given string belongs to a regular language
using the Pumping Lemma.

Implement a Moore Machine that produces

6 outputs based only on the current state.

Implement a Mealy Machine that

7 produces outputs based on the current
state and input symbol.

Implement a parser for a simple

8 arithmetic expression using Context- Free
Grammar (CFG).

Implement a Python program that converts

9 a given Context-Free Grammar (CFG) into
Chomsky Normal Form (CNF).

Implement a Pushdown Automaton

10 (PDA) to recognize the language {a^n b^n
| n ≥ 1}.

TOTAL

7
Theory of Computation (3164203) Enrollment no:230280152068

8
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 1: Regular Expressions and Finite Automata

Objective : Implement a Python script to check if a given string matches a regular expression.

import re

pattern = r"1(0+1)*0$"
print("Target Pattern:", pattern)
print("Target Pattern:", pattern)

Target Pattern: 1(0+1)*0$

while True:
user_input = input("Enter a string to check: ").strip()

if user_input.lower() == "exit":
print("Exiting program")
break

if [Link](pattern, user_input):
print("SUCCESS!", user_input, "belongs to the language.")

else:
print("REJECTED!", user_input, "does not belong to the language.")

print("-" * 30)

Enter a string to check: 1010

SUCCESS! 1010 belongs to the language.
------------------------------
Enter a string to check: 10010
SUCCESS! 10010 belongs to the language.
------------------------------
Enter a string to check: 1011
REJECTED! 1011 does not belong to the language.
------------------------------
Enter a string to check: 0110
REJECTED! 0110 does not belong to the language.
------------------------------
Enter a string to check: exit
Exiting program

9
Theory of Computation (3164203) Enrollment No:230280152068

10
Theory of Computation (3164203) Enrollment No:230280152068

Practical 2: Deterministic Finite Automata(DFA)

 Objective: Implement a DFA that recognizes binary strings divisible by 3.

def dfa_divisible_by_3(binary_string):
transition = {
0: {'0': 0, '1': 1},
1: {'0': 2, '1': 0},
2: {'0': 1, '1': 2}
}

state = 0

for bit in binary_string:

if bit not in ['0', '1']:
return "Invalid binary string"
state = transition[state][bit]

if state == 0:
return "Accepted"
else:
return "Rejected"

while True:
binary_input = input("\nEnter binary string: ")

if binary_input.lower() == "exit":
print("Program stopped.")
break

result = dfa_divisible_by_3(binary_input)
print(result)

Enter binary string:

Accepted

Enter binary string: 11

Accepted

Enter binary string: 101

Rejected

Enter binary string: 110

Accepted

Enter binary string: exit

Program stopped.

11
Theory of Computation (3164203) Enrollment No:230280152068

12
Theory of Computation (3164203) Enrollment No:230280152068

Practical 3: NFA to DFA Conversion

 Objective: Convert a given NFA to DFA

from collections import defaultdict

def nfa_to_dfa(states, alphabet, transitions, start_state, final_states):

dfa_states = []
dfa_transitions = {}
dfa_final_states = []

start = frozenset([start_state])
dfa_states.append(start)
unprocessed = [start]

while unprocessed:
current = [Link]()
dfa_transitions[current] = {}

for symbol in alphabet:

next_state = set()

for state in current:

if (state, symbol) in transitions:
next_state.update(transitions[(state, symbol)])

next_state = frozenset(next_state)
dfa_transitions[current][symbol] = next_state

if next_state not in dfa_states:

dfa_states.append(next_state)
[Link](next_state)

for state in dfa_states:

if any(s in final_states for s in state):
dfa_final_states.append(state)

return dfa_states, dfa_transitions, dfa_final_states

states = input("Enter NFA states : ").split(",")

alphabet = input("Enter alphabet symbols : ").split(",")

n = int(input("Enter number of transitions: "))

transitions = {}

print("Enter transitions in format: state symbol next_states")

for _ in range(n):
state, symbol, next_states = input().split()
transitions[(state, symbol)] = set(next_states.split(","))

start_state = input("Enter start state: ")

final_states = set(input("Enter final states : ").split(","))

dfa_states, dfa_transitions, dfa_final_states = nfa_to_dfa(

states, alphabet, transitions, start_state, final_states
)

print("\nDFA States:")
for state in dfa_states:
print(set(state))

print("\nDFA Transitions:")
for state in dfa_transitions:
for symbol in alphabet:
print(f"{set(state)} --{symbol}--> {set(dfa_transitions[state][symbol])}")

print("\nDFA Final States:")

for state in dfa_final_states:
print(set(state))

13
Theory of Computation (3164203) Enrollment No:230280152068
Enter NFA states : q0,q1,q2
Enter alphabet symbols : 0,1
Enter number of transitions: 3
Enter transitions in format: state symbol next_states
q0 0 q0,q1
q0 1 q0
q1 0 q2
Enter start state: q0
Enter final states : q2

DFA States:
{'q0'}
{'q0', 'q1'}
{'q0', 'q1', 'q2'}

DFA Transitions:
{'q0'} --0--> {'q0', 'q1'}
{'q0'} --1--> {'q0'}
{'q0', 'q1'} --0--> {'q0', 'q1', 'q2'}
{'q0', 'q1'} --1--> {'q0'}
{'q0', 'q1', 'q2'} --0--> {'q0', 'q1', 'q2'}
{'q0', 'q1', 'q2'} --1--> {'q0'}

DFA Final States:

{'q0', 'q1', 'q2'}

14
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 4: DFA Minimization

Objective: Implement a Python program that minimizes a given Deterministic Finite Automaton (DFA)

def minimize_dfa(states, alphabet, transitions, start_state, final_states):

P = [set(final_states), set(states) - set(final_states)]

while True:
new_P = []

for group in P:
partition_map = {}

for state in group:

signature = []

for symbol in alphabet:

next_state = transitions[state][symbol]

for i, p in enumerate(P):
if next_state in p:
[Link](i)
break

signature = tuple(signature)

if signature not in partition_map:

partition_map[signature] = []

partition_map[signature].append(state)

for part in partition_map.values():

new_P.append(set(part))

if new_P == P:
break

P = new_P

state_map = {}
for i, group in enumerate(P):
for state in group:
state_map[state] = f"Q{i}"

new_states = set(state_map.values())
new_start = state_map[start_state]
new_finals = {state_map[s] for s in final_states}

new_transitions = {}

for group in P:
rep = list(group)[0]
new_state = state_map[rep]
new_transitions[new_state] = {}

for symbol in alphabet:

new_transitions[new_state][symbol] = state_map[transitions[rep][symbol]]

print("\n===== Minimized DFA =====")

print("States:", new_states)
print("Alphabet:", alphabet)
print("Start State:", new_start)
print("Final States:", new_finals)

print("\nTransitions:")
for state in new_transitions:
for symbol in alphabet:
print(f"δ({state}, {symbol}) → {new_transitions[state][symbol]}")

# States
states = input("Enter states (comma separated): ").split(',')

# Alphabet
alphabet = input("Enter alphabet symbols (comma separated): ").split(',')
15
Theory of Computation (3164203) Enrollment No:230280152068

print("\nEnter transitions:")
transitions = {}

for state in states:

transitions[state] = {}
for symbol in alphabet:
next_state = input(f"δ({state},{symbol}) = ")
transitions[state][symbol] = next_state

start_state = input("\nEnter start state: ")

final_states = input("Enter final states (comma separated): ").split(',')

minimize_dfa(states, alphabet, transitions, start_state, final_states)

Enter states (comma separated): A,B,C,D

Enter alphabet symbols (comma separated): 0,1

Enter transitions:
δ(A,0) = B
δ(A,1) = C
δ(B,0) = A
δ(B,1) = D
δ(C,0) = D
δ(C,1) = A
δ(D,0) = C
δ(D,1) = B

Enter start state: A

Enter final states (comma separated): D

===== Minimized DFA =====

States: {'Q1', 'Q2', 'Q0', 'Q3'}
Alphabet: ['0', '1']
Start State: Q2
Final States: {'Q0'}

Transitions:
δ(Q0, 0) → Q3
δ(Q0, 1) → Q1
δ(Q1, 0) → Q2
δ(Q1, 1) → Q0
δ(Q2, 0) → Q1
δ(Q2, 1) → Q3
δ(Q3, 0) → Q0
δ(Q3, 1) → Q2

16
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 5: Pumping Lemma for Regular Languages

Objective: Implement a Python program to check if a given string belongs to a regular language using the Pumping Lemma.

import re

def check_pumping_lemma(word, p, in_language):

# Check the word's length against the pumping length.

if len(word) < p:
return f"Error: The word length ({len(word)}) is shorter than the pumping length ({p}). Choose a longer wo

if not in_language(word):
return "Error: The initial word you entered is not even in the chosen language!"

print(f"\nTesting word: '{word}' (Length: {len(word)}) with pumping length: {p}")

print("-" * 40)

# Split the word into parts xyz such that |y| > 0 and |xy| <= p.
for i in range(p): # 'i' is the end index of x (length of x)
for j in range(i + 1, p + 1): # 'j' is the end index of y
x = word[:i]
y = word[i:j]
z = word[j:]

valid_split = True
for k in range(6): # Test pumping y from 0 to 5 times
pumped_word = x + (y * k) + z

if not in_language(pumped_word):
print(f"Failed split: x='{x}', y='{y}', z='{z}'. Pumped {k} times -> '{pumped_word}' (NOT in
valid_split = False
break

# If a split survives all pumps, the language passes the lemma for this specific word
if valid_split:
print(f"Successful split: x='{x}', y='{y}', z='{z}'. All pumped variations stay in the language."
return "\nResult: Valid pumping split found! The language satisfies the pumping lemma for this wo

# If no valid pumping exists

return "\nResult: No valid pumping exists. All possible splits failed. The language is NOT regular."

def is_an_bn(s):
"""Returns True if the string is exactly a^n b^n"""
n = len(s)
if n % 2 != 0:
return False
half = n // 2
return s[:half] == 'a' * half and s[half:] == 'b' * half

def main():
print("=== Pumping Lemma Interactive Checker ===")

# 1. Take a language as input (via menu or regex)

print("Select a language to test:")
print("1. L = { a^n b^n | n >= 0 } (Non-Regular)")
print("2. L = { a* b* } (Regular)")
print("3. Custom Regular Expression (Regular)")

choice = input("\nEnter your choice (1/2/3): ").strip()

if choice == '1':
lang_func = is_an_bn
lang_desc = "a^n b^n"
elif choice == '2':
lang_func = lambda s: bool([Link](r'a*b*', s))
lang_desc = "a* b*"
elif choice == '3':
user_regex = input("Enter your custom Python regex (e.g., a+b+c): ").strip()
try:
[Link](user_regex) # Validate regex
lang_func = lambda s: bool([Link](user_regex, s))

17
Theory of Computation (3164203) Enrollment No:230280152068
lang_desc = f"Regex: {user_regex}"
except [Link]:
print("Invalid Regular Expression.")
return
else:
print("Invalid choice. Exiting.")
return

# Take a word and pumping length as input

word = input(f"\nEnter a word to test against the language [{lang_desc}]: ").strip()

try:
p = int(input("Enter the pumping length (p): ").strip())
except ValueError:
print("Pumping length must be an integer. Exiting.")
return

# Run the algorithm

result = check_pumping_lemma(word, p, lang_func)
print(result)

if __name__ == "__main__":
main()

=== Pumping Lemma Interactive Checker ===

Select a language to test:
1. L = { a^n b^n | n >= 0 } (Non-Regular)
2. L = { a* b* } (Regular)
3. Custom Regular Expression (Regular)

Enter your choice (1/2/3): 3

Enter your custom Python regex (e.g., a+b+c): ([01])*01

Enter a word to test against the language [Regex: ([01])*01]: 110101

Enter the pumping length (p): 3

Testing word: '110101' (Length: 6) with pumping length: 3

----------------------------------------
Successful split: x='', y='1', z='10101'. All pumped variations stay in the language.

Result: Valid pumping split found! The language satisfies the pumping lemma for this word.

18
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 6: Moore Machine Simulation

Objective: Implement a Moore Machine that produces outputs based only on the current state.

class MooreMachine:
def __init__(self, states, alphabet, transitions, outputs, initial_state):
# Step 1: Define the Moore Machine
[Link] = states
[Link] = alphabet
[Link] = transitions
[Link] = outputs
self.initial_state = initial_state

def process_string(self, input_string):

# Step 2: Set the initial state
current_state = self.initial_state
output_sequence = []
path = [] # To keep track of the path for printing

# Validate input string against alphabet

for symbol in input_string:
if symbol not in [Link]:
return None, None, f"Error: Symbol '{symbol}' is not in the alphabet {[Link]}."

print(f"\nProcessing string: '{input_string}'")

print("-" * 40)

# Step 3: Read the input string symbol by symbol

for symbol in input_string:
[Link](current_state)

# Step 4: Append the output corresponding to the current state before moving
output_sequence.append([Link][current_state])

# Step 5: Transition to the next state based on the input symbol

current_state = [Link][current_state][symbol]

# Step 6: Append the output of the final state after processing all symbols
[Link](current_state)
output_sequence.append([Link][current_state])

return output_sequence, path, "Success"

def main():
print("=== Interactive Moore Machine Simulator ===")
print("Select a Moore Machine to test:")
print("1. Machine A: Outputs '1' whenever the sequence ends with '10' (Alphabet: 0, 1)")
print("2. Machine B: Counts number of 'a's modulo 3 (Outputs 0, 1, or 2) (Alphabet: a, b)")

choice = input("\nEnter your choice (1/2): ").strip()

if choice == '1':
# Machine A: Detects sequence "10"
states = ['q0', 'q1', 'q2']
alphabet = ['0', '1']
initial_state = 'q0'
outputs = {'q0': '0', 'q1': '0', 'q2': '1'}
transitions = {
'q0': {'0': 'q0', '1': 'q1'},
'q1': {'0': 'q2', '1': 'q1'},
'q2': {'0': 'q0', '1': 'q1'}
}
machine = MooreMachine(states, alphabet, transitions, outputs, initial_state)
print("\n[Loaded Machine A: Sequence '10' detector]")

elif choice == '2':

# Machine B: Modulo 3 counter for 'a'
states = ['S0', 'S1', 'S2']
alphabet = ['a', 'b']
initial_state = 'S0'
outputs = {'S0': '0', 'S1': '1', 'S2': '2'}
transitions = {
'S0': {'a': 'S1', 'b': 'S0'},
'S1': {'a': 'S2', 'b': 'S1'},
'S2': {'a': 'S0', 'b': 'S2'}
}

19
Theory of Computation (3164203) Enrollment No:230280152068
machine = MooreMachine(states, alphabet, transitions, outputs, initial_state)
print("\n[Loaded Machine B: 'a' Modulo 3 counter]")

else:
print("Invalid choice. Exiting.")
return

user_string = input(f"Enter an input string using alphabet {[Link]}: ").strip()

# Run the machine

outputs, path, status = machine.process_string(user_string)

if status != "Success":
print(status)
return

# Print the step-by-step trace

print("Step-by-step trace:")
for i in range(len(user_string)):
print(f" In state {path[i]}, output is '{outputs[i]}'. Read '{user_string[i]}' -> transition to {path[i
print(f" Final state is {path[-1]}, output is '{outputs[-1]}'.")
print("-" * 40)

# Step 7: Print the generated output sequence

final_output_string = "".join(outputs)
print(f"Final Output Sequence: {final_output_string}")

if __name__ == "__main__":
main()

=== Interactive Moore Machine Simulator ===

Select a Moore Machine to test:
1. Machine A: Outputs '1' whenever the sequence ends with '10' (Alphabet: 0, 1)
2. Machine B: Counts number of 'a's modulo 3 (Outputs 0, 1, or 2) (Alphabet: a, b)

Enter your choice (1/2): 1

[Loaded Machine A: Sequence '10' detector]

Enter an input string using alphabet ['0', '1']: 11010

Processing string: '11010'

----------------------------------------
Step-by-step trace:
In state q0, output is '0'. Read '1' -> transition to q1
In state q1, output is '0'. Read '1' -> transition to q1
In state q1, output is '0'. Read '0' -> transition to q2
In state q2, output is '1'. Read '1' -> transition to q1
In state q1, output is '0'. Read '0' -> transition to q2
Final state is q2, output is '1'.
----------------------------------------
Final Output Sequence: 000101

20
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 7: Mealy Machine Simulation

Objective: Implement a Mealy Machine that produces outputs based on the current state and input symbol.

class MealyMachine:
def __init__(self, states, input_alphabet, output_alphabet, transitions, outputs, initial_state):
# Define the Mealy Machine
[Link] = states
self.input_alphabet = input_alphabet
self.output_alphabet = output_alphabet
[Link] = transitions
[Link] = outputs
self.initial_state = initial_state

def process_string(self, input_string):

# Set the initial state
current_state = self.initial_state
output_sequence = []
path = [current_state]

for symbol in input_string:

if symbol not in self.input_alphabet:
return None, None, f"Error: Symbol '{symbol}' is not in the alphabet {self.input_alphabet}."

print(f"\nProcessing string: '{input_string}'")

print("-" * 45)

for symbol in input_string:

current_output = [Link][current_state][symbol]
output_sequence.append(current_output)

# Use the transition function to move to the next state

next_state = [Link][current_state][symbol]
current_state = next_state

[Link](current_state)

# Continue until the input string is fully processed (Loop completes)

return output_sequence, path, "Success"

def main():
print("=== Interactive Mealy Machine Simulator ===")
print("Select a Mealy Machine to test:")
print("1. Machine A: 1's Complement Generator (Flips 0s to 1s and 1s to 0s)")
print("2. Machine B: '101' Sequence Detector (Outputs 'Y' when '101' is found, else 'N')")

choice = input("\nEnter your choice (1/2): ").strip()

if choice == '1':

states = ['q0']
input_alphabet = ['0', '1']
output_alphabet = ['0', '1']
initial_state = 'q0'

transitions = {
'q0': {'0': 'q0', '1': 'q0'}
}
outputs = {
'q0': {'0': '1', '1': '0'} # If input is 0 output 1, if input is 1 output 0
}

machine = MealyMachine(states, input_alphabet, output_alphabet, transitions, outputs, initial_state)

print("\n[Loaded Machine A: 1's Complement Generator]")

elif choice == '2':

# Detects overlapping sequence "101"
states = ['q0', 'q1', 'q2']
input_alphabet = ['0', '1']
output_alphabet = ['Y', 'N'] # Y = Detected, N = Not Detected
initial_state = 'q0'

21
Theory of Computation (3164203) Enrollment No:230280152068
transitions = {
'q0': {'0': 'q0', '1': 'q1'},
'q1': {'0': 'q2', '1': 'q1'},
'q2': {'0': 'q0', '1': 'q1'}
}
# Output is 'Y' ONLY when in state q2 (saw "10") and input is '1' (completing "101")
outputs = {
'q0': {'0': 'N', '1': 'N'},
'q1': {'0': 'N', '1': 'N'},
'q2': {'0': 'N', '1': 'Y'}
}

machine = MealyMachine(states, input_alphabet, output_alphabet, transitions, outputs, initial_state)

print("\n[Loaded Machine B: '101' Sequence Detector]")

else:
print("Invalid choice. Exiting.")
return

# Take the input string from the user

user_string = input(f"Enter an input string using alphabet {machine.input_alphabet}: ").strip()

# Run the machine

outputs_seq, path, status = machine.process_string(user_string)

if status != "Success":
print(status)
return

# Print the step-by-step trace

print("Step-by-step trace:")
for i in range(len(user_string)):
print(f" In state {path[i]}, read '{user_string[i]}' -> output '{outputs_seq[i]}' & move to {path[i+1]}
print("-" * 45)

# Print the generated output sequence

final_output_string = "".join(outputs_seq)
print(f"Final Output Sequence: {final_output_string}")

if __name__ == "__main__":
main()

=== Interactive Mealy Machine Simulator ===

Select a Mealy Machine to test:
1. Machine A: 1's Complement Generator (Flips 0s to 1s and 1s to 0s)
2. Machine B: '101' Sequence Detector (Outputs 'Y' when '101' is found, else 'N')

Enter your choice (1/2): 2

[Loaded Machine B: '101' Sequence Detector]

Enter an input string using alphabet ['0', '1']: 110101

Processing string: '110101'

---------------------------------------------
Step-by-step trace:
In state q0, read '1' -> output 'N' & move to q1
In state q1, read '1' -> output 'N' & move to q1
In state q1, read '0' -> output 'N' & move to q2
In state q2, read '1' -> output 'Y' & move to q1
In state q1, read '0' -> output 'N' & move to q2
In state q2, read '1' -> output 'Y' & move to q1
---------------------------------------------
Final Output Sequence: NNNYNY

22
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 8: Context-Free Grammar (CFG) Parsing

Objective: Implement a parser for a simple arithmetic expression using Context- Free Grammar (CFG).

import re

class RecursiveDescentParser:
def __init__(self, expression):
# Lexer Step: Tokenize the input string
token_pattern = r'\d+|\+|\-|\*|\/|\(|\)'
# Remove spaces and extract tokens
[Link] = [Link](token_pattern, [Link](' ', ''))
[Link] = 0
self.current_token = [Link][[Link]] if [Link] else None

def advance(self):
"""Moves to the next token in the input."""
[Link] += 1
if [Link] < len([Link]):
self.current_token = [Link][[Link]]
else:
self.current_token = None

def parse(self):
"""Starts parsing and checks if the entire expression is valid."""
if not [Link]:
return False, "Empty expression"
try:
[Link]()

# If we finished parsing and no tokens are left, it's valid

if self.current_token is None:
return True, "Valid Expression! Successfully parsed."
else:
return False, f"Invalid: Unexpected token at end: '{self.current_token}'"

except Exception as e:
return False, f"Invalid: {str(e)}"

# --- Step 1 & 2: Grammar Rules & Recursive Functions ---

def expr(self):
"""Rule 1: E -> T ((+ | -) T)*"""
[Link]()
while self.current_token in ('+', '-'):
[Link]()
[Link]()

def term(self):
"""Rule 2: T -> F ((* | /) F)*"""
[Link]()
while self.current_token in ('*', '/'):
[Link]()
[Link]()

def factor(self):
"""Rule 3: F -> Number | ( E )"""
if self.current_token is None:
raise Exception("Unexpected end of expression.")

if self.current_token.isdigit():
[Link]()

elif self.current_token == '(':

[Link]()
[Link]()

if self.current_token == ')':
[Link]()
else:
raise Exception("Missing closing parenthesis ')'.")
else:
raise Exception(f"Syntax error near '{self.current_token}'. Expected a number or '('.")

23
Theory of Computation (3164203) Enrollment No:230280152068
def show_grammar():
print("\n--- Context-Free Grammar (CFG) Rules ---")
print("This parser uses the following rules to avoid left-recursion:")
print("1. Expression (E) -> T (+ T | - T)*")
print("2. Term (T) -> F (* F | / F)*")
print("3. Factor (F) -> Number | ( E )")
print("----------------------------------------")

def main():
while True:
print("\n=== CFG Parser for Arithmetic Expressions ===")
print("1. Parse a mathematical expression")
print("2. View Context-Free Grammar (CFG) rules")
print("3. Exit")

choice = input("Enter your choice (1-3): ").strip()

if choice == '1':
user_expr = input("\nEnter an arithmetic expression (e.g., 3 + 5 * (2 - 8)): ")
print("-" * 50)
print(f"Parsing: '{user_expr}'")

parser = RecursiveDescentParser(user_expr)
is_valid, message = [Link]()

if is_valid:
print(f"Result: [SUCCESS] {message}")
else:
print(f"Result: [FAILED] {message}")
print("-" * 50)

elif choice == '2':

show_grammar()

elif choice == '3':

print("Exiting Parser. Goodbye!")
break

else:
print("Invalid choice. Please enter 1, 2, or 3.")

if __name__ == "__main__":
main()

=== CFG Parser for Arithmetic Expressions ===

1. Parse a mathematical expression
2. View Context-Free Grammar (CFG) rules
3. Exit
Enter your choice (1-3): 1

Enter an arithmetic expression (e.g., 3 + 5 * (2 - 8)): (4 + 6) * 3 - 2

--------------------------------------------------
Parsing: '(4 + 6) * 3 - 2'
Result: [SUCCESS] Valid Expression! Successfully parsed.
--------------------------------------------------

=== CFG Parser for Arithmetic Expressions ===

1. Parse a mathematical expression
2. View Context-Free Grammar (CFG) rules
3. Exit
Enter your choice (1-3): 2

--- Context-Free Grammar (CFG) Rules ---

This parser uses the following rules to avoid left-recursion:
1. Expression (E) -> T (+ T | - T)*
2. Term (T) -> F (* F | / F)*
3. Factor (F) -> Number | ( E )
----------------------------------------

=== CFG Parser for Arithmetic Expressions ===

1. Parse a mathematical expression
2. View Context-Free Grammar (CFG) rules
3. Exit
Enter your choice (1-3): 3
Exiting Parser. Goodbye!

24
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 9: Convert CFG to Chomsky Normal Form (CNF)

Objective: Implement a Python program that converts a given Context-Free Grammar (CFG) into Chomsky Normal Form (CNF).

import itertools

def is_terminal(symbol):
print(f"{lhs} -> {' | '.join(productions)}")
"""Assume lowercase letters are terminals, uppercase are Non-terminals."""
return [Link]()

def print_grammar(grammar, step_name):

print(f"\n--- {step_name} ---")
for lhs, rhs_list in [Link]():
productions = ["".join(p) for p in rhs_list]
print(f"{lhs} -> {' | '.join(productions)}")

# Remove epsilon (e) productions

def remove_epsilon_productions(grammar):
new_grammar = {k: [list(p) for p in v] for k, v in [Link]()}

nullables = set()
for lhs, rhs_list in new_grammar.items():
if ['e'] in rhs_list:
[Link](lhs)

for lhs, rhs_list in new_grammar.items():

new_rhs = []
for production in rhs_list:
if production == ['e']:
continue

# Find indices of nullable variables in this production

nullable_indices = [i for i, sym in enumerate(production) if sym in nullables]

for i in range(len(nullable_indices) + 1):

for combo in [Link](nullable_indices, i):
new_prod = [sym for idx, sym in enumerate(production) if idx not in combo]
if new_prod and new_prod not in new_rhs:
new_rhs.append(new_prod)

new_grammar[lhs] = new_rhs

return new_grammar

# Remove unit productions (A -> B)

def remove_unit_productions(grammar):
new_grammar = {k: [list(p) for p in v] for k, v in [Link]()}

while True:
unit_found = False
for lhs, rhs_list in list(new_grammar.items()):
for production in rhs_list:
# If production is exactly one Non-terminal (Unit production)
if len(production) == 1 and not is_terminal(production[0]):
unit_found = True
unit_var = production[0]

new_grammar[lhs].remove(production)

if unit_var in new_grammar:
for unit_prod in new_grammar[unit_var]:
if unit_prod not in new_grammar[lhs]:
new_grammar[lhs].append(unit_prod)
if not unit_found:
break

return new_grammar

# Eliminate long productions (A -> BCD...)

def remove_long_productions(grammar):
new_grammar = {}
new_var_counter = 1

25
Theory of Computation (3164203) Enrollment No:230280152068
for lhs, rhs_list in [Link]():
new_grammar[lhs] = []
for production in rhs_list:
current_lhs = lhs
current_prod = list(production)

while len(current_prod) > 2:

new_var = f"X{new_var_counter}"
new_var_counter += 1

# Create a rule for the first symbol and the new variable
new_grammar.setdefault(current_lhs, []).append([current_prod[0], new_var])

current_lhs = new_var
current_prod = current_prod[1:]

new_grammar.setdefault(current_lhs, []).append(current_prod)

return new_grammar

def convert_mixed_terminals(grammar):
new_grammar = {}
terminal_vars = {} # Maps 'a' -> 'Y_a'

for lhs, rhs_list in [Link]():

new_grammar[lhs] = []
for production in rhs_list:
# Only affect rules with exactly 2 symbols
if len(production) == 2:
new_prod = []
for sym in production:
if is_terminal(sym):

if sym not in terminal_vars:

term_var = f"Y_{sym}"
terminal_vars[sym] = term_var
new_grammar[term_var] = [[sym]]
new_prod.append(terminal_vars[sym])
else:
new_prod.append(sym)
new_grammar[lhs].append(new_prod)
else:
new_grammar[lhs].append(production)

return new_grammar

# Main execution logic

if __name__ == "__main__":
# Define the starting grammar as a dictionary
# Example: S -> ASA | aB, A -> B | S | e, B -> b | e
# 'e' represents epsilon (empty string)
initial_grammar = {
'S': [['A', 'S', 'A'], ['a', 'B']],
'A': [['B'], ['S'], ['e']],
'B': [['b'], ['e']]
}

print_grammar(initial_grammar, "Initial Grammar")

grammar_no_e = remove_epsilon_productions(initial_grammar)
print_grammar(grammar_no_e, "After Removing Epsilon Productions")

grammar_no_unit = remove_unit_productions(grammar_no_e)
print_grammar(grammar_no_unit, "After Removing Unit Productions")

grammar_no_long = remove_long_productions(grammar_no_unit)
print_grammar(grammar_no_long, "After Eliminating Long Productions (>2 symbols)")

final_cnf_grammar = convert_mixed_terminals(grammar_no_long)
print_grammar(final_cnf_grammar, "Final Chomsky Normal Form (CNF)")

--- Initial Grammar ---

S -> ASA | aB
A -> B | S | e
B -> b | e

--- After Removing Epsilon Productions ---

26
Theory of Computation (3164203) Enrollment No:230280152068
S -> ASA | SA | AS | S | aB | a
A -> B | S
B -> b

--- After Removing Unit Productions ---

S -> ASA | SA | AS | aB | a
A -> b | ASA | SA | AS | aB | a
B -> b

--- After Eliminating Long Productions (>2 symbols) ---

S -> AX1 | SA | AS | aB | a
X1 -> SA
A -> b | AX2 | SA | AS | aB | a
X2 -> SA
B -> b

--- Final Chomsky Normal Form (CNF) ---

S -> AX1 | SA | AS | Y_aB | a
Y_a -> a
X1 -> SA
A -> b | AX2 | SA | AS | Y_aB | a
X2 -> SA
B -> b

27
Theory of Computation (3164203) Enrollment No:230280152068

28
Theory of Computation (3164203) Enrollment No:230280152068

 Practical 10: Pushdown Automata (PDA) Simulation

Objective: Implement a Pushdown Automaton (PDA) to recognize the language {a^n b^n | n ≥ 1}.

def simulate_pda(input_string):
# Initialize PDA with start state and empty stack
stack = []
current_state = 'q0'

if not input_string:
print("Error: String is empty. Language requires n >= 1.")
return False

print(f"Processing string: '{input_string}'")

print("-" * 45)

# Read input string one symbol at a time

for symbol in input_string:
print(f"State: {current_state} | Symbol: '{symbol}' | Stack before: {stack}")

if symbol == 'a':
if current_state == 'q0':

[Link]('a')
else:
print(" -> REJECTED: Encountered 'a' after 'b's started.")
return False

elif symbol == 'b':

if current_state == 'q0':
current_state = 'q1'

if current_state == 'q1':
# Pop 'a' from the stack for each 'b' encountered
if len(stack) > 0:
[Link]()
else:
print(" -> REJECTED: Stack underflow (More 'b's than 'a's).")
return False
else:
print(f" -> REJECTED: Invalid symbol '{symbol}' found.")
return False

print(f" -> Stack after: {stack}\n")

# If the stack is empty at the end, accept the string

if len(stack) == 0 and current_state == 'q1':
return True
else:
if len(stack) > 0:
print(" -> REJECTED: Stack not empty at end (More 'a's than 'b's).")
return False

if __name__ == "__main__":
# Take input string and loop until 'exit' is entered
user_string = ""
while user_string.lower() != 'exit':
user_string = input("Enter an input string (e.g., aaabbb): for exit enter 'exit'").strip()

if user_string.lower() == 'exit':
print("Exiting program.")
break

print("\n")
is_valid = simulate_pda(user_string)

print("-" * 45)
if is_valid:
print(f"FINAL RESULT: The string '{user_string}' is ACCEPTED.")
else:
print(f"FINAL RESULT: The string '{user_string}' is REJECTED.")

Enter an input string (e.g., aaabbb): for exit enter 'exit'aaabbb

Processing string: 'aaabbb'

29
Theory of Computation (3164203) Enrollment No:230280152068
---------------------------------------------
State: q0 | Symbol: 'a' | Stack before: []
-> Stack after: ['a']

State: q0 | Symbol: 'a' | Stack before: ['a']

-> Stack after: ['a', 'a']

State: q0 | Symbol: 'a' | Stack before: ['a', 'a']

-> Stack after: ['a', 'a', 'a']

State: q0 | Symbol: 'b' | Stack before: ['a', 'a', 'a']

-> Stack after: ['a', 'a']

State: q1 | Symbol: 'b' | Stack before: ['a', 'a']

-> Stack after: ['a']

State: q1 | Symbol: 'b' | Stack before: ['a']

-> Stack after: []

---------------------------------------------
FINAL RESULT: The string 'aaabbb' is ACCEPTED.
Enter an input string (e.g., aaabbb): for exit enter 'exit'aabbbb

Processing string: 'aabbbb'

---------------------------------------------
State: q0 | Symbol: 'a' | Stack before: []
-> Stack after: ['a']

State: q0 | Symbol: 'a' | Stack before: ['a']

-> Stack after: ['a', 'a']

State: q0 | Symbol: 'b' | Stack before: ['a', 'a']

-> Stack after: ['a']

State: q1 | Symbol: 'b' | Stack before: ['a']

-> Stack after: []

State: q1 | Symbol: 'b' | Stack before: []

-> REJECTED: Stack underflow (More 'b's than 'a's).
---------------------------------------------
FINAL RESULT: The string 'aabbbb' is REJECTED.
Enter an input string (e.g., aaabbb): for exit enter 'exit'exit
Exiting program.

30