Important Automata Interview Questions Part – 2
Differentiate Between (a,b) And (a+b)?
(a, b) =
Represents a and b.
(a + b) =
Represents either a or b.
What Is The Difference Between Gt And Gtg ?
In TG, there are transitions for the strings. While in GTG, one can write whole RE as a transition from one state to another one.
How To Create A Re Of A Particular Language?
Regular expression is used to express the infinite or finite language, these RE are made in such a way that these can generate the strings of that unique language also for the cross check that the defined RE is of a specified language that RE should accept all the string of that language and all language strings should be accepted by that RE.
How Diagrams Of Fa’s Are Created ?
It depends upon the question how many states involve in a FA. There is not any formal procedure to design FA for a language. This ability just improves with time and practice.
Every FA is also a TG but not every TG is FA. In every FA, every state shows transition of all letters of given alphabet but in any TG it is not must. In TG, we may or may not show all letters transition according to requirement. We can also show transitions on reading any strings in TGs but it is not possible in FAs.
What Is The Difference Between Fa’s ,and Tg’s ?
There are two or three big differences between FA’s and TG’s.
In FA there can be maximum one initial or starting state while in TG there may be more than one initial state.
In FA there can be transition for letters only while in TG transitions from a state to another one can be for strings.
In FA there must be transition from each state for each letter (deterministic) while in TG there may be no transition for specific letter from a state and there may be more than one path for a string or letter from a state.
What Is The Exact Definition Of Fa ?
Definition:
A Finite automaton (FA), is a collection of the followings
Finite number of states, having one initial and some (maybe none) final states.
Finite set of input letters (Ó) from which input strings are formed.
Finite set of transitions i.e. for each state and for each input letter there is a transition showing how to move from one state to another.
What Is The Concept Of Nondeterministic Finite Automaton (nfa) ?
Nondeterminism plays a key role in the theory of computing. A nondeterministic finite state automaton is one in which the current state of the machine and the current input do not uniquely determine the next state. This just means that a number of subsequent states (zero or more) are possible next states of the automaton at every step of a computation.
Of course, nondeterminism is not realistic, because in real life, computers must be deterministic. Still, we can simulate nondeterminism with deterministic programs. Furthermore, as a mathematical tool for understanding computability, nondeterminism is invaluable.
As with deterministic finite state automata, a nondeterministic finite state automaton has five components.
a set of states
a finite input alphabet from which input strings can be constructed
a transition function that describes how the automaton changes states as it processes an input string
a single designated starting state
a set of accepting states
The only difference lies in the transition function, which can now target subsets of the states of the automaton rather than a single next state for each state, input pair.
If A Language Can Be Expressed In The Form Of Fa Than Why It Is Needed To Use Nfa ?
NFA stands for non-deterministic FA and this sort of structure has relaxation compared with FA. So it is rather more easy to represent a language using NFA.
We have methods to convert NFA into FA’s so sometimes it is easier to build NFA of a given language and than convert its NFA into FA using these methods rather than directly building an FA for a language which may be very difficult.
How To Made Nfa Corresponding To The Closure Of An Fa ?
While generating NFA corresponding to closure of an FA one should take care of the null string. Simple way to accept null string is declare initial state, final as well. But in this way a lot of other strings will also be accepted.
Therefore, accurate way is draw another state. Declare the new state initial as well as final. Connect the new state with the states originally connected with the old start state with the same transitions as the old start state. Newly drawn diagram will be an NFA representing the language closure of the given FA
How Moore And Mealy Machine Works In Computer Memory What Is Their Importance In Computing ?
Mealy & Moore Machines work in computing as incrementing machine & 1’s complement machine etc. These operations as basic computer operations so these machines are very important.
What Is The Significance Of Pumping Lemma Ii ?
The significance of 2nd version of ‘pumping lemma’ is that there are some infinite non regular languages like PALINDROME we can built FA that can accept there certain words but if we increase the length of their words that FA don’t accept these words so by pumping lemma version I it is very difficult to prove them non regular but with the second version we can prove that a language is Non regular even it’s some words may be accepted by some FA’s.
Moore And Mealy Machine?
In order to run a string on a Mealy or Moore machine, you can take directions from transition table. Running string on Mealy or Moore machine is similar to running string on a FA. For example, if want to run abba on the machine, take start from initial state.
Check what is the transition for a, what state it goes. After that check what is the path of b from that state and so on. In this way you will be able to run whole of the string. Note that there is no final state in Mealy or Moore machine. So there is no case of acceptance or rejection of string.
You just have to determine what the output is. I hope that will clear your mind for further clarification please listens to your lecture carefully.
The string is taken for the testing purposes. You can take any sort of string and determine its output using machine.
What Is The Difference Between Semiword And Word Please Also Give An Example Regarding This?
Word:
A word is complete combinations of terminals only e.g. abba or ab or a or null string.
Semiword:
A semiword is a string of terminals (may be none) concatenated with exactly one nonterminal on the right i.e. a semi word, in general, is of the following form (terminal)(terminal) ——- (terminal)(nonterminal)
For example
aaaaaaB , aabbaaaA , A.
What Is The Difference Between Derivation Tree And Total Tree ?
A Derivation tree is the one that shows how to derive any specific word of the language described by CFG but Total Language Tree shows all words of the Language described by CFG on it.
What Does Mean The Language Is Closed?
When we say that a Language is closed it is always with respect to certain operation.
A simple example may be that the set of integers is closed under addition. It means when we take two numbers from set of integers say 3, 7 the result of their addition would also be in the set of integers.
Similarly if the result of an operation on the words of a language results in the word of the same language we say that the language is closed under that operation.
What Are The Productions?
Productions are the grammatical rules and regulations. These rules express the behavior of CFG. Using production in CFG terminals are converted into non-terminals and when all the terminals are converted using productions, a word is acquired.
What Is The Difference Between Concatenation And Intersection Of Two Fa’s Also What Is The Difference Among Union Of Two Fa’s And Addition Of Them?
In intersection of two FA’s only those strings are accepted which are independently accepted by both FA’s, while in concatenation of two FA’s only those strings will be accepted in which first part of string is accepted by first FA and remaining part of string is accepted by the second FA.
While taking union of two FA’s one can represent it using + sign. So (FA1 U FA2) and (FA + FA2) both are same. There is no difference between them.
Is It Possible To Make Cfg For Infix And Post-fix Expression’s Using Derivation Tree ?
Derivation tree is only used to derive words of language that is described by a CFG. Yes, we can create CFG for languages infix expressions, postfix expressions.
What Is The Uses Of Push Down Automata In Computing ?
PDA is just an enhancement in FAs. i.e Memory is attached with machine that recognizes some language. FA is basic structure for most advanced electronic machines such as computer etc.
What Is Difference Between Push Down Stack And Push Down Store ?
No difference at all. Both terms are used to describe memory structure attached with FAs to store some characters in it.
What Is Meant By The Terms Stack Consistence And Input Tape Consistence ?
Term Stack consistent means we can pop any character from the top of the stack only. PDA should not be able to pop any character other than that is present on the top of the stack.
Term Tape consistent means we can read only the first letter on the tape not any other letter of the tape after the first one.
What Is Unit Production?
The production in which one non-terminal leads to only one non-terminal.