VIVA QUESTIONS FOR AUTOMATA LANGUAGES AND COMPUTATION
1.Why a finite automaton is called finite?
2.What does the symbol ∑ ;in the formal definition of finite automata ;denotes?
3.The language accepted by a finite automaton is known as a _________ language.
4.Differentiate between regular expressions, regular languages and regular grammars?
5.Define Kleene closure and positive closure of a set.
6.Explain the difference between context sensitive grammars and context freegrammars.
7.What is a sentential form?
8.When is a contecxt free language called inherently ambigous?
9.When do we say that a context free language is in chomsky normal form?
10.What are the useless symbols of a grammar?
11.Define unit productions
12.What are ∈ -productions?
13.What does the symbol Г denotes in the definition of Pushdown Automata?
14.Differentiate between multi-tape Turing Machine and multi-track Turing Machine.
15.What is Chomsky Hierarchy?
16.Which is the machine that accepts context sensitive languages?
17.What are recursively enumerable languages?
18.Mention some applications for automata languages and computation
VIVA ANSWERS FOR AUTOMATA LANGUAGES AND COMPUTATION
1.Since the number of states in an automaton are finite.2.An alphabet called the input alphabet.
3.Regular
4.Regular Languages – languages that are accepted by finite automata. Regular expressions – short hand notation for denoting regular languages. Regular grammarsare restricted forms of context free grammars (left linear and right linear) which generates the regular languages
5.The application of the Kleene star to a set V is written as V*.a.If V is a set of strings then V* is defined as the smallest superset of V thatcontains ε (the empty string) and is closed under the string concatenationoperation. This set can also be described as the set of strings that can bemade by concatenating zero or more strings from V. b.If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.If remove { ∈ } from V*, the resulting set denoted by V + is called the positive closure.
6.A context-free grammar is a grammar in which the left-hand side of each productionrule consists of only a single nonterminal symbol. This restriction is non-trivial; notall languages can be generated by context-free grammars. Those that can are called context-free languages. A context sensitive grammar has productions of the form α → β , where both of them are in (V ∪ T)*, In this a production will happen only ina particular context.
7.A sentential form is the start symbol S of a grammar or any string in (V union T)*that can be derived from S. Consider the linear grammar ({S, B}, {a, b}, S, {S goesto aS, Sgoes toB, Bgoes tobB, Bgoes toempty string}).A derivation using thisgrammar might look like this: S directly derives aS directly derives aB directlyderives abB directly derives abbB directly derives abb Each of {S, aS, aB, abB,abbB, abb} is a sentential form.
8.If all the grammars generating a Context free language are ambigous then thelanguage is said to be inherently ambigous.
9.If all the productions in that grammar are either in the form A→BC or A→a andthere are no other types of production, we can say that the given context freegrammar is in Chomsky normal form.
10. A symbol X ∈ V is useless if a.there is no derivation from X to any string in the language (non-terminating) b.there is no derivation from S that reaches a sentential form containing X(non-reachable)
11.Productions of the form A → B. All other productions including A→a are non-unit
12.Productions of the form A→ ∈
13.Stack alphabet
14.Multi-tape machine has multiple tapes and separate heads for each tape, multi-track machine has only a single tape divided in to multiple tracks and a single head to readall the tracks
15.
16.Linear bounded automaton
17.A language is recursively enumerable if some Turing machine accepts it.
0 comments:
Post a Comment