CS402 - Theory of Automata

Home Page
Q & A
Online Test
1The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by the ………… production treesOneTwoMore than oneAt most oneC
2In a STACKThe element PUSHed first is POPed firstThe element PUSHed first is POPed in the lastThe element PUSHed in last is POPed in lastNone of given optionsB
3Consider the following CFG: (NOTE: ^ means NULL) S->a|Xb|aYa X->Y|^ Y->b|X Which Nonterminal(s) is/are NOT nullableSXYS,X and YB
4If a CFG has only productions of the form nonterminal -> string of two nonterminals or nonterminal -> one terminal then the CFG is said to be in _________PDA formChomsky Normal Form (CNF)NULL able formUnit production formB
5The structure given below is called _________ S -> aA|bB A -> aS|a B -> bS|bRETGCFGPDAC
6(a* + b*)* = (a + b)* this expression is __________TrueFalseNANAB
7The states in which there is no way to leave after entry are calledDavey John LockersDead StatesWaste BasketsAll of the given optionsD
8If S = {ab, bb}, then S* will not containAbbbabBbbaababbbbbbbabB
9According to theory of automata there1234B
10What do automata mean?Something done manuallySomething done automaticallyBoth of theseNone of theseB
11What is false about the term alphabet?It is a finite set of symbolsIt is usually denoted by Greek letter sigmaIt can be an empty setStrings are made up of its elementsC
12Formal is also known as _________Syntactic languageSemantic languageInformal languageNone of theseA
13Kleene star closure can be definedOver any set of stringOver specific type of stringOver any set of languageOver specific type of languageA
14While finding RE corresponding to TG, we connect the new start state to the old start state by the transition labeled byABnull stringNone of the given optionsC
15(a* + b*)* = (a + b)* this expression is __________TrueFalseNANAB
16The states in which there is no way to leave after entry are calledDavey John LockersDead StatesWaste BasketsAll of the given optionsD
18According to theory of automata there are _________ types of languages1234B
19A DFA with n states must accept at least one string of length greater than nTrueFalseNANA 
20Σ={a,Aa,Abb}, then string aAaAbbAa has ________ length1234D
21Languages generated by kleene star are always __________FiniteInfiniteSometimes finite & sometimes infiniteNone of the theseB
22Let S = {aa, bb} be a set of strings then s* will haveΛabbaaabbbaabbaabA
23If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)* will be generated by(r1)(r2)(r1 + r2)(r2)*(r1)*B
24If a language can be expressed through FA, then it can also be expressed through TGTrueFalseDepends on languageNone of the aboveA
25Above given FA accepts the language in which stringsBegins with and ends in same letterBegins with and ends in different letterHas length more than 2None of the givenA
26GTG can have _______________ final state01More than 1All of the givenD
27In GTG, if a state has more than one incoming transitions from a state. Then all those incoming transitions can be reduced to one transition using _____________ sign-+*None of the givenB
28“One language can be expressed by more than one NFA”. This statement is ___________TrueFalseDepends on NFANone of the givenA
29One FA has 3 states and 2 letters in the alphabet. Then FA will have ___________ number of transitions in the diagram4567C
30If an alphabet has n number of letter, then number of strings of length m will ben+m(n)(m)m^nn^mD
31“Every finite language can be expressed by FA”. This statement is __________TrueFalseDepends on languageNone of theseA