Download PTU B.Tech 2021 Jan IT 5th Sem 78256 Formal Language And Automata Theory Question Paper

FirstRanker.com

B.Tech. (IT) (Sem.-5)

FORMAL LANGUAGE & AUTOMATA THEORY

--- Content provided by FirstRanker.com ---

Subject Code : BTIT-501-18

M.Code : 78256

Time : 3 Hrs. Max. Marks : 60

INSTRUCTION TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.

--- Content provided by FirstRanker.com ---

2. SECTION-B contains FIVE questions carrying FIVE marks each and students has to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students has to attempt any TWO questions.

SECTION-A

Answer briefly :

1. Define Finite Automaton.

--- Content provided by FirstRanker.com ---

2. What are various properties of transition function?
3. Define grammar and language.
4. Differentiate between left and right context in languages.
5. Define yield in CFG.
6. Define ambiguity in CFG.

--- Content provided by FirstRanker.com ---

7. Define TM.
8. Define the term acceptability in PDA.
9. Give instantaneous description of Turing machine.
10. Differentiate between DFA and NDFA.

SECTION-B

--- Content provided by FirstRanker.com ---

11. Write a note on canonical derivations.
12. Discuss the formal properties of LL(k) and LR(k) grammars.
13. Explain the concept of ambiguity with the help of example.
14. Construct a Moore machine equivalent to the Mealy machine M defined by following table :

15. Find a reduced grammar equivalent to the given grammar.
    

    --- Content provided by FirstRanker.com ---

    S → AB A → a B → b B → C E → c

SECTION-C

16. Write a note on cellular automaton and rewriting systems.
17. Design PDA for {a^mbⁿ | m > n}
18. Design Turing machine of {0ⁿ1ⁿ | n >= 1}

--- Content provided by FirstRanker.com ---

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any page of Answer Sheet will lead to UMC against the Student.

FirstRanker.com