Formal Language and Automata Theory || What is FLAT
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.