Formal Language and Automata Theory (FLAT)

This article will help you understand the concept of FLAT through multiple questions & answers and increase your professional as well as academic knowledge.

Let us start with the fundamentals of the topic.

Define Automata and its type with a suitable diagram?

 The term “Automaton “(plural automata) is derived from the  Greek word “αὐτόματα,” which means “self-acting”. Automata is the abstract model of a digital computer. It has a mechanism of reading input which is written on an input file to which the automata can read but not change. 

It follows a predetermined sequence of operations automatically.

Types of Automata:
1. Deterministic Automata
2. Non-Deterministic Automata

Deterministic Automata: A deterministic automaton is a concept of automata theory in which the outcome of a transition from one state to another is determined by the input. A common deterministic automaton is a DFA (deterministic finite automaton).

Non-Deterministic Automata: In non-deterministic automata, it is not defining the move of automata at each point. An NDA may have several possible moves. So, we can only predict a set of possible actions, not move. A common non-deterministic automaton is an NFA(non-deterministic finite automata).

Define the Algorithm and its types?

 An algorithm is a finite set of rules which gives a sequence of operations of solving a specific problem. The structure of an algorithm can be defined as: 

• The input step 
• The assignment step 
• The decision step 
• The repetitive step
•  The output step

Types of an algorithm:

1. Deterministic algorithm: After the execution of each step of an algorithm. The control logic comes to the decision box with two paths one for yes and one for no.

2. Non-Deterministic algorithm: If the algorithm is capable of exploring a large number of alternatives simultaneously to reach out to a correct solution. We can call it NDA. E.g.: Race  Condition.

3. Random algorithm: If after executing some step the control logic transfer to another step of the algorithm as dictated by the random device. E.g.: coin tossing.

4. Infinite algorithm: An algorithm whose loop is running continues to give us better and better estimates of the results. e.g.: digital clock.

Define the flow chart and draw a flowchart to find all the roots of a quadratic equation

      ax2+bx+c=0. 

 A flow chart is a graphical representation of a specific sequence of steps of an algorithm.  It consists of a diagram of characteristically shaped boxes connected by directed line segments.

Flowchart to calculate roots of quadratic equation ax2+bx+c=0.

Define the Term?

Alphabet in Automata

Ans – An alphabet can be defined as a finite set of symbols. These are the input symbols from which strings are constructed by Appling certain operation in automata theory we denote alphabet or input symbol by the set ∑. e.g.: ∑ ={0,1}.

String in automata

Ans – Combine some symbols with each other by applying some rules we get a string. The string can be also obtained by applying operation on a particular symbol itself. E.g.: { abc}.

Language in automata

Ans – The alphabet is a set of string from a  language while using some criteria. E.g. let us consider the set of all-natural number N or set of even number etc.

Grammar in automata
Ans –  The language of grammar is the set of all string that can be generated from that grammar.