Implementing a DFA in C++: Acceptance Criteria and Transition States

This homework assignment involves simulating a Deterministic Finite Automation (DFA) using the C++ programming language. The program is designed with three states and uses a string of infinite language S as input. It accepts strings only when the first and last characters match and result in identical starting and ending states within the DFA, specifically strings that start with '1'. For instance, the input string '100121' will be accepted because both its initial and final states are the same (q1), while '100112' is rejected due to different starting and ending states. This assignment emphasizes understanding DFA basics without using data structures since DFAs lack memory concepts. The implementation strictly adheres to the requirements of taking only strings beginning with '1', ensuring correctness in outputs as demonstrated by provided examples.

Runninghead: DFA SIMULATION USING C++
DFA SIMULATION USING C++
Name of the Student:
Name of the University:
Author Note:

1DFA SIMULATION USING C++
Deterministic Finite Automation or DFA is an automata where the next stage that a machine will
move to can be predetermined. It is called finite as it has a finite number of states (Heinz 2017).
In this program, a DFA with 3 states has been taken. Here the alphabet used is a string of infinite
language S. In a DFA, the string or language is accepted only when the first and last state of the
DFA matches. In this program, for easy understanding of the basics, a string which must start
with 1 is taken as input. So for example, if a string is 100112, when the program is run with this
input, the string is not accepted as the first character does not match with the last character and
the first and last states also comes different. In this example, q1 and q2 are the transition states
shown. However, when we take a string say 100121, the first and last character match and we
also get same first and last states. Hence, it is accepted. The main criteria for a DFA to accept
a string is that it should produce the same first and final states. Here the code provided is
written in a very simple manner to reduce complexity in order to demonstrate the basic
functioning of a DFA. Data structures have not been used as DFAs do not have the concept of
memory (Chan 2018). The code is written in C++ language as mentioned in the requirement.
Figure 1Code Image

2DFA SIMULATION USING C++
Figure 2Output 1
Figure 3Output 2
The First image provided shows the code used for writing the program. It is written in C++
language.
The Second image provided shows the Output for the “Not accepted” String input.
The Second image provided shows the Output for the “String accepted” String input.
Note: Only take strings starting with “1” as other string inputs may lead to faulty outputs.

3DFA SIMULATION USING C++
References:
Heinz, J., 2017. Theoretical Computational Linguistics: Learning Theory.
Chan, S.O., 2018. Formal Languages and Automata Theory.