 Algorithm
 Compiler Design
 Computer Fundamentals
 Computer Networks
 Computer Organization & Architecture
 DBMS
 Digital logic
 Information System
 Ms Office
 Operating System
 Programming & Data structure
 Software Engineering
 Software Testing
 System Programming
 Theory of computation
 Web technology
 Analog & Digital Circuits
 Control System
 Electronic Devices
 EMFT
 Junctions, Diodes & Tunnel
 Signals & systems
 Wireless Communication
 Engineering Mechanics
 Fluid Mechanics
 Heat Transfer
 I.C. Engines
 Power Engineering
 Strength of Materials
 Theory of Machines
 Thermodynamics
 Concrete Structure
 Construction & Structure engineering
 Costing & Valuation of Building Materials
 Errors & Adjustments
 Hydraulics
 Soil Mechanics
 Steel Structures
 Structural Analysis
 Surveying
 Traffic Engineering
 Water supply & waste water engineering
Computer Science/IT
Electronics & communications
Mechanical Engineering
Civil engineering
Electrical engineering


( 1 ) Let w be any string of length n is {0,1}*.Let L be the set of all substrings of w. What is the minimum number of states in a nondeterministic finite automaton that accepts L?
 1) n1
 2) n
 3) n+1
 4) 2n1

Show Answer Report Discussion in forumAnswer : 3) n+1
Solution : We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of "010" and it has 4 states.
fig shows the NFA that accepts all substrings of 010, the substrings are: 0, 01, 10 and 010
discussion
Answer : 3) n+1



( 2 ) The minimum state automaton equivalent to the above FSA has the following number of states
 1) 1
 2) 2
 3) 3
 4) 4

Show Answer Report Discussion in forumAnswer : 2) 2
Solution : q0 and q1 are the states that are required at most and hence the minium number of states is 2
discussion
Answer : 2) 2



( 3 ) Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11
 1) [(00(0+1)* 11] + [11( 0 + 1)* 00]
 2) [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)].
 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
 4) (00+11) (0+1)* (00+11).

Show Answer Report Discussion in forumAnswer : 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
Solution : The regular expression can be categorized into two subparts.
R= L_{1}+L_{2}
L_{1}= the strings which begin with 00 or 11.
L_{2}= the strings which end with 00 or 11.
Let us find out L_{1} and L_{2}.
L_{1}= (00 + 11) (any number of 0's and 1's )
L_{1} = (00 + 11) (0+1)*
Similarly L_{2} = (any number of 0's and 1's ) ( 00 + 11) = (0+1)* (00 + 11)
Hence R= [(00+11) (0+1)*] + [( 0 + 1)* (00+11)].
discussion
Answer : 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]



( 4 ) The language L = { 0^{i} 2 1 ^{i} i>0 } over the alphabet (0,1,2) is
 1) not recurcise
 2) is recursive and deterministic CFL
 3) is a regular language
 4) is not a deterministic CFL but a CFL

Show Answer Report Discussion in forumAnswer : 2) is recursive and deterministic CFL
Solution : Let us first design a deterministic pushdown automata for the given language.
For each occurrence of '0' , we PUSH X in the stack.
When '2' appears, no stack operation is performed. But, state of the automata is changed.
For each occurrence of '1' , we POP X from the stack.
If at the end Z0 is on the stack top then input string is accepted
We also design a Turing machine for the given language.
When '0' appears in the input string , we replace it with X .Then, traverse to the rightmost corner and replace '1' with Y.
We go back to the leftmost '0' and repeat the above process.
While traversing rightwards from the beginning of the input string, if after X, '2' appears and after '2', Y appears then we reach the HALT state.
Thus, the given language is recursive. Every recursive language is a CFL.
discussion
Answer : 2) is recursive and deterministic CFL



( 5 ) A given grammar is called ambiguous if
 1) two or more productions have the same nonterminal on the left hand side
 2) a derivation tree has more than one associated sentence
 3) there is a sentence with more than one derivation tree corresponding to it
 4) brackets are not present in the grammar

Show Answer Report Discussion in forumAnswer : 3) there is a sentence with more than one derivation tree corresponding to it
Solution :
discussion
Answer : 3) there is a sentence with more than one derivation tree corresponding to it



( 6 ) A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
 1) 15 States
 2) 11 states
 3) 10 states
 4) 9 states

Show Answer Report Discussion in forumAnswer : 1) 15 States
Solution :
discussion
Answer : 1) 15 States



( 7 ) In a contextfree grammar
 1) ε can't be the right hand side of any production
 2) terminal symbols can't be present in the left hand side of any production
 3) number of grammar symbols in the left hand side is not greater than the number of grammar symbols in the right hand side
 4) all of these

Show Answer Report Discussion in forumAnswer : 4) all of these
Solution :
discussion
Answer : 4) all of these



( 8 ) If s is a string over (0 + 1)* then let n_{0} (s) denote the number of 0's in s and n_{1} (s)the number of l's in s. Which one of the following languages is not regular?
 1) L = {s € (0 + 1)*n_{0} (s) is a 3digit prime
 2) L = {s € (0 + 1)*  for every prefix s' of s, l 0 (s')  n_{1} (s')  <= 2 }
 3) L={s € (0+1)*  n_{0}(s)  n_{1}(s)  <= 4}
 4) L = {s € (0 + 1)  n_{0} (s) mod 7 = n_{1} (s) mod 5 = 0 }

Show Answer Report Discussion in forumAnswer : 3) L={s € (0+1)*  n_{0}(s)  n_{1}(s)  <= 4}
Solution :
discussion
Answer : 3) L={s € (0+1)*  n_{0}(s)  n_{1}(s)  <= 4}



( 9 ) Let SHAM_{3} be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM_{3} be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
 1) Both DHAM_{3} and SHAM_{3} are NPhard
 2) SHAM_{3} is NPhard, but DHAM_{3} is not
 3) DHAM_{3} is NPhard, but SHAM_{3} is not
 4) Neither DHAM_{3} nor SHAM_{3} is NPhard

Show Answer Report Discussion in forumAnswer : 1) Both DHAM_{3} and SHAM_{3} are NPhard
Solution : There is a difference between SHAM and DHAM, that SHAM is used for finding a hamiltonian cycle in a graph but DHAM is the problem of determining if a graph exists in a Hamiltonian cycle. Also it is given that v id divisible by 3, hence the problem can be reduced from 3 SAT which further determines that SHAM and DHAM are NP hard
discussion
Answer : 1) Both DHAM_{3} and SHAM_{3} are NPhard



( 10 ) For two regular languages
L_{1} = (a + b)* a and L_{2} = b (a + b ) *, the intersection of L_{1} and L_{2} is given by  1) (a + b ) * ab
 2) ab (a + b ) *
 3) a ( a + b ) * b
 4) b (a + b ) * a

Show Answer Report Discussion in forumAnswer : 4) b (a + b ) * a
Solution :
discussion
Answer : 4) b (a + b ) * a
