flat

UNIT – 1

1) Define string, alphabet and language. Explain operations on strings and languages

2) Explain DFA mathematically with an example

3) Explain NFA mathematically with an example

4) Construct DFA for the given languages over a given alphabet.

5) Construct NFA for the given languages over a given alphabet

UNIT – 2

 1) Construct NFA without €-moves for a given transition diagram with €-moves

2) Convert given NFA to DFA

3)Construct  Moore and Mealy machines that accepts strings over {0,1} where if the input ends in 001 , output a A; if the input ends in 100,output a B; else output a C

4) Find the Minimum state Finite Automaton equivalent to the given transition diagram

5) Check whether the given two finite state machines are equivalent or not

UNIT – 3

1) Explain identity rules

2) Construct Regular Expression for the given Finite Automata

3) Construct finite automaton for the regular expression

3) Explain closure properties of the regular sets

4) Explains pumping lemma theorem with an example

UNIT – 4

1) Construct Right linear and left linear grammar for the given finite automaton or regular expression

2) Construct finite automaton for the given regular grammar

3) Explain context free grammar with examples

4) Find the left most derivation and right most derivation of a given string context free grammar

5) Find out derivation trees or parse trees of a given string for the given context free grammar

 download