Question Bank
Add a question- Construct Moore machine equivalent to the mealy machine described below.
- Define epsilon closure. Find epsilon closures for all the states of given NFA-E. Remove epsilons with out changing the acceptance.
- Discuss any three of the following briefly. (a) Decidability of problems (b) Undecidability of post correspondence problem. (c) P and NP problems. (d) RICE's theorem.
- Construct LR(0) items for the grammar given, find its equivalent DFA. Check the parsing by taking a suitable derived string.
- Giving the basic steps involved in designing a Turing Machine design a Turing Machine which accepts the strings derived form {0.1} and have even number ones.
- What is the type of production to derive a recursive enumerable languages, which machine accepts these languages.
- Give CFG for generating sets of even palindromes over the string {a,b}.
- Convert the following grammar into Chomsky Normal Form S -> aA/a/B/C A -> aB/E B -> aA C -> cCD D -> abd
- Construct left linear and right linear grammar for the regular expression. 0*(1(0+1))*
- Give the regular expressions accepted by following FA. Figure 3
- Construct FA equivalence to the following regular expression r = ((0 + 1(1 + 01)*00)*
- Minimise the Finite automation given below and show both the given and the reduced one are equivalent.
- Construct the Moore machine for given Melay machine.
- Construct a DFA equivalent
- Give DFA which reads strings from {a,b} and end with aaa.
- Show that the following post correspondence problem has a solution and give the solution.
- What is decidability? Explain any two undecidable problems.
- Write short notes on: DCFL and DPDA
- Write short notes on: LR(k) grammar
- Write short notes on: C.S. languages.
- Design Turing Machine to accept even palindromes derived from the input {a,b}. Give its Transition table and diagram also.
- What is delta of a Turing Machine, explain functions involved in a move of Turing Machines in detail.
- Prove that acceptance by empty stack and by final state is equivalent.
- Design a PDA which accepts all strings which can be derived from the following Grammar. Taking a suitable example verify the machine. S -> aB/bA A -> a/aS/bAA B -> b/bS/aBB
- Give the CFG to generating the following sets The set of palindromes over alphabet {a,b}
- Obtain the regular grammar to accept the strings containing even number of zeroes.
- Show that the set is not regular. State and explain the theorem used.
- State and explain closure properties of regular sets.
- Construct a DFA for the regular expression 10 + (0+11) 0*1 and optimize the states.
- Construct the Moore machine for Figure 1 Melay machine.
- Minimise the Finite automation Figure 2 below and show both the given and the reduced one are equivalent.
- For the following state transition table draw the state transition diagram. Find its equivalent machine. For the string abbaaab test whether both give same result or not. q0 is the initial state and q3 is the Final state.