Using AI to Solve Automata Theory Problems

Ankit1, Amandeep2, Dharmender Kumar', Keshav Kumar•, Surajs

M.Sc. Computer Science'•'·', Artificial Intelligence and Data Science, GJUS&T,

Assistant Professor', Artificial Intelligence and Data Science, GJUS&T, Professor', Artificial Intelligence and Data Science, GJUS&T,

Email - ankitkumar14384@gmail.com https://orcid.org/0009-0008-6940-6937

Abstract

Many students find automata theory tough due to its extensive use of mathematical and logical reasoning. The aim of this project was to test whether AI models like ChatGPT or Gemini could help solve simple automata problems. For example, given a language, can they construct a DFA/NFA? A mini program was created where the AI creates an answer which is verified by checking script which tests that answer to some sample strings. When we tested ChatGPT on 6 small problems, only �33% of the answers were fully correct. So, at least in this basic setup, the AI is not reliable. This report presents a small trial, not a complete system. A further, larger test with a synthetic dataset comprising 1000 automata (where each automaton has one small controlled edit, akin to a software mutation) shows that even a single such edit normally flips the correct accept/reject label on around half of a set of witness strings. Further, the identification of the type of edit from behaviour alone came close to random

Keywords: automata theory, Al, language models, DFA, NFA, mutation testing,fault sensitivity, student project