[JNTU-H] 2-2 Semister R13 2015 FLAT 2&3 marks Important Questions

[JNTU-H] Btech 2nd year 2-2 Semister R13 Regulation 2015 

FLAT (FORMAL LANGUAGES AND AUTOMATA THEORY)  

Exam 2&3 marks Important Questions :-

a) Define the terms alphabet, string, prefix, suffix, language give examples to each.

b) Give DFA & NFA which accept the language { (10)n : n 0 }

c) Define a linear grammar

d) Define a ambiguous CFG

e) Construct a CFG for the set of all strings over the alphabet {a,b} with exactly twice 10

as many a’s and b’s.

f) Distinguish between DPDA and NPDA

g) Explain the operations of a NPDA with diagram?

h) Define unrestricted grammar.

i) What is the modified version of PCP

a) What are Universal Turing Machines

b) Define computations of a TM?

c) Define CFG and What are its advantages

d) Define unit production.

e) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

f) Compare NFA & DFA

g) Write a note on applications of formal languages and automata.

h) Define regular expression ,Give a regular expression for L={anbm : n 4, m3}

i) Prove or disprove the following for regular expressions r,s,and t (rs+r)r=r(sr+r)*

a) Give a description about FA with empty moves

b) Define regular grammar with example.

c) Give the set and explain in English the sets denoted by following regular expressions.

i) (11+0) (00+1)

ii) (1+01+001)(0+00)

iii) (0+1)00(0+1)

iv) 0 1 2

v) 00 11 22

d) Explain dependency graph & its applications in CFG.

e) Prove the substitution rule of context free grammar?

f) Give a CFG generating the following set that is the set of palindromes over alphabet{a,b}

g) Let G be the grammar

a) Find the DFA that recognizes the set of all string on Σ={a,b} starting with the prefix “ab”

b) Construct a DFA & NFA to accept all string in {a,b} such that every “a” has one “b” immediately 8 to its right ?

c) Find all strings in L ((a+b)*b(a+ab)*) of length less than four

d) Prove the following identities for regular expression r,s and t here r=s means 6

L(r)=L(s) r+s=s+r, (rs)t=r(st),(r+s)t=rt+st

e) Find the NFA that accepts the language L{ab*aa+bba*ab)

f) What are CFG’s Give CFG for the language L= {an b2n | n>0}

g) Define context free grammars formally. Give some examples .

h) Why FAs are less powerful than the PDA’s