Automata Interview Questions and Answers
Question - 31 : - What Is The Difference Between Semiword And Word Please Also Give An Example Regarding This?
Answer - 31 : -
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.
Answer - 32 : -
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.
Question - 33 : - What Does Mean The Language Is Closed?
Answer - 33 : -
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.
Question - 34 : - What Are The Productions?
Answer - 34 : -
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.
Question - 35 : - 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?
Answer - 35 : -
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.
Question - 36 : - Is It Possible To Make Cfg For Infix And Post-fix Expression’s Using Derivation Tree ?
Answer - 36 : -
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.
Question - 37 : - What Is The Uses Of Push Down Automata In Computing ?
Answer - 37 : -
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.
Question - 38 : - What Is Difference Between Push Down Stack And Push Down Store ?
Answer - 38 : -
No difference at all. Both terms are used to describe memory structure attached with FAs to store some characters in it.
Question - 39 : - What Is Meant By The Terms Stack Consistence And Input Tape Consistence ?
Answer - 39 : -
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.
Question - 40 : - What Is Unit Production?
Answer - 40 : -
The production in which one non-terminal leads to only one non-terminal.