Automata Interview Questions and Answers
Question - 41 : - What is Left most Derivation in CFG?
Answer - 41 : -
It is a method of generation of strings from a CFG starting from left most letter of the string.
Question - 42 : - In the lecture 41 ‘s example, we have converted PDA to conversion form and a word ‘aaaabb’ is derived from this conversion form PDA. What are the derivation steps.
Answer - 42 : -
The PDA converted to conversion form has some specific features that are important to understand first. These features are
The states named START, READ, HERE and ACCEPT are called joints of the machine.
With the help of the conversion form we have been able to achieve that POP state has only one path out of it and the path taking (multiple paths) decisions take place only on the READ state.
The word ‘aaaabb’ is generated as follows from the PDA
START-POP4-PUSH $
This step pops $ and then pushes it to ensure that stack contains $ at the beginning.
READ1-POP6-PUSH $-PUSH a
As first time after reading “a” there is $ at the top of stack so we will follow path segment READ1-POP6-PUSH $-PUSH a
READ1-POP5-PUSH a-PUSH a
Now a is on the top of the stack so we will follow READ1-POP5-PUSH a-PUSH a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP5-PUSH a-PUSH a
Again following same segment for a
READ1-POP1- HERE-POP2
As we read b on input tape.
READ2-POP1-HERE-POP2
As we read b on input tape.
READ2-POP3-ACCEPT.
As we read ∆ from the input tape
Question - 43 : - How to differentiate between “wanted” and “unwanted branch” ?
Answer - 43 : -
When we derive a word in Top down parsing beginning with the starting Non Terminal the branches of the tree that do not lead to our required word are left aside these branches are called unwanted branches.
For example for CFG
S—–>AA
A—–>a | b
If we want to generate the word “aa” we will leave the branch generated by the production A——>b.
Question - 44 : - What is the difference between intersection and union of a language?
Answer - 44 : -
Intersection of two languages will consist of all those words which are in both languages while union of two languages will consist of all those words which are present in at least one language.
Symbol for intersection is ∩ and for union is U.
Question - 45 : - What is the difference between Context free languages and regular languages?
Answer - 45 : -
Regular languages can be represented by FA’s because we do not need any memory to recognize (accept or reject them on FA) them but there is another class of languages that can not be represented by FA’s because these languages require that we have some memory (with the help of memory we can store letters of the string we are checking so that we can compare them with next coming letters in the string).
For example language anbn requires that we must store a’s and then compare their count with next coming b’s so that we can check whether a’s are equal to b’s or not.
Due to this reason we use Context Free Grammars to represent them because we can5t write RE’s for them.
So Context Free Languages represent a broader category this category also include regular languages as subcategory. It means that context free languages include regular languages as well as some other languages.
Question - 46 : - What is the difference between Moore and Mealey machines?
Answer - 46 : -
In Mealy Machine we read input string letters and generate output while moving along the paths from one state to another while in Moore machine we generate output on reaching the state so the output pattern of Moore machine contains one extra letter because we generated output for state q0 where we read nothing.
Question - 47 : - What does the following terms mean
Answer - 47 : -
i. STACK Consistent
ii. Y-able Paths
iii. Working string
iv. Semi Word means
Stack consistence means that in the PDA converted in the conversion form, when we follow a path segment (which is formed by combining start, read or here state with next read, here or accept state on the path) along the PDA its pop state should have the path for the same letter that is present on the top of the stack at that stage. If this doesn’t happen our PDA will crash because in conversion form of the PDA the pop state has only one letter path, so if we could not be able to find that letter on the top of the stack our PDA will crash (if will not find path where to go from that state)
Working string means the string present on the input tape.
Y-able Paths means that when we follow a certain sequence of rows from the row table to generate a path for a word form start state to accept state. The path (sequence of rows) should be stack as well as joint consistent it means that rows should end at the same read or here state (join consistency ) and the rows should be able to pop the letter from the top that is indicated in the pop state of the row.
Semi word is the string of terminals it may be null string ending with a Non terminals on the right.
Question - 48 : - Is Automata Theory is a Programming Subject or theoretical?
Answer - 48 : -
Automata theory is the study of abstract computing devices, or “machines”. This topic goes back to the days before digital computers and describes what is possible to compute using an abstract machine.These ideas directly apply to creating compilers, programming languages, and designing applications. They also provide a formal framework to analyze new types of computing devices, e.g. biocomputers or quantum computers
What are practical Examples of the implications of Automata Theory and the formal Languages?
Grammars and languages are closely related to automata theory and are the basis of many important software components like:
- · Compilers and interpreters
- · Text editors and processors
- · Text searching
- · System verification
Question - 49 : -
What are the Types of Automata?
Answer - 49 : -
- · The Types of Automata Theory are
- · Finite Automata
- · Regular Languages
- · Linear-bounded Automata
- · Context Sensitive Languages
- · Push-Down Automata
- · Context Free Languages
- · Turing Machines
- · Recursively innumerable languages
There are others as well like,
- · Random Access Machines
- · Parallel Random Access Machines
- · Arrays of Automata
Question - 50 : - How types of Automata Differ?
Answer - 50 : -
They differ in the following areasComplexity (or Simplicity)
Power
In the function that can be computed.
In the languages that can be accepted.