Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
_____________________________________________________________________________________
Push down machine represents
_____________________________________________________________________________________
The behavior of a NFA can be stimulated by DFA
_____________________________________________________________________________________
_____________________________________________________________________________________
_____________________________________________________________________________________
Which of the following is not primitive recursive but partially recursive?
_____________________________________________________________________________________
Consider the following grammar.
S ::= AB
A ::= a
A ::= BaB
B ::= bbA
Which of the following is false?
_____________________________________________________________________________________
Set of regular languages over a given alphabet set,is not closed under
_____________________________________________________________________________________
Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains
_____________________________________________________________________________________
LL grammar for the language L = {a^{n} b^{m} c^{n} +m | m=0, n=0} is
_____________________________________________________________________________________
The logic of pumping lemma is a good example of
_____________________________________________________________________________________
If every string of a language can be determined whether it is legal or illegal in finite time the language is called
_____________________________________________________________________________________
Context free language can be recognized by
_____________________________________________________________________________________
Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)
_____________________________________________________________________________________
Given the following productions of a grammar :
_____________________________________________________________________________________
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.
_____________________________________________________________________________________
_____________________________________________________________________________________
The regular expression for the following DFA
_____________________________________________________________________________________
FSM can recognize
_____________________________________________________________________________________
Assume statements S1 and S2 defined as :
S_{1} : L_{2} -L_{1} is recursive enumerable where L_{1} and L_{2} are recursive and recursive enumerable respectively.
S2 : The set of all Turing machines is countable.
Which of the following is true ?
_____________________________________________________________________________________
Which of the following is the most general phase structured grammar ?
_____________________________________________________________________________________
A FSM can be used to add how many given integers?
_____________________________________________________________________________________
The language accepted by the nondeterministic pushdown automaton
_____________________________________________________________________________________
Consider the following statements : I. Recursive languages are closed under complementation. II. Recursively enumerable languages are closed under union. III. Recursively enumerable languages are closed under complementation. Which of the above statements are true ?
_____________________________________________________________________________________
6 Files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 records repectively.
In what order should they be sorted so as to optimize activity? Assume each file is accessed with the same frequency.
F3,F4,F1,F5,F6,F2
F2,F6,F5,F1,F4,F3
F1,F2,F3,F4,F5,F6
Ordering is immaterial as all files are accessed with the same frequency
_____________________________________________________________________________________
Following grammar
S-> bS
S -> b
S -> aA
A -> bA
_____________________________________________________________________________________
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is ~L also context-free?
3) If L is regular language, then, is ~L also regular?
4) If L is recursive language, then, is ~L also recursive?
_____________________________________________________________________________________
The language L={a^{k } b^{k} |k>=1} is
_____________________________________________________________________________________
All strings having equal number of a and b can be recognized by
_____________________________________________________________________________________
The basic limitation of a FSM is that
_____________________________________________________________________________________
How many states can a process be in ?
_____________________________________________________________________________________
Which one of the following statement is false ?
_____________________________________________________________________________________
Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
_____________________________________________________________________________________
Which is not the correct statement(s) ? (i) Every context sensitive language is recursive. (ii) There is a recursive language that is not context sensitive.
_____________________________________________________________________________________
A formal grammar is a___________for rewriting strings.
_____________________________________________________________________________________
Finite automata are used for pattern matching in text editors for
_____________________________________________________________________________________
Two finite states are equivalent if they
_____________________________________________________________________________________
A PDM behaves like a TM when the number of auxiliary memory it has is
_____________________________________________________________________________________
Which of the following permanent database that has an entry for each terminal symbol ?
_____________________________________________________________________________________
The language accepted by finite automata is
_____________________________________________________________________________________
The following CFG S®aB|bA, A®a|as|bAA, B®b|bs|aBB generates strings of terminals that have
_____________________________________________________________________________________
An FSM can be used to add two given integers.This remark is
_____________________________________________________________________________________
Context free languages are not closed under
_____________________________________________________________________________________
Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below :
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
_____________________________________________________________________________________
Which of the following is most powerful?
_____________________________________________________________________________________
Which of the following statements is/are FALSE? (1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. (2) Turing recognizable languages are closed under union and complementation. (3) Turing decidable languages are closed under intersection and complementation (4) Turing recognizable languages are closed under union and intersection.
_____________________________________________________________________________________
_____________________________________________________________________________________
Finite state machine___________recognize palindromes.
_____________________________________________________________________________________
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
_____________________________________________________________________________________
If two finite state machines are equivalent they should have the same number of
_____________________________________________________________________________________