Theory Of Automata Formal Languages (KCA201) - AKTU Question Paper 2024-25

consecutive 0’s or 1’s.}

Q0 { Q 0}     {Q1}
Q1   {Q2}   {Q2}
Draw the transition diagram of NFA with null transition from above table.
Convert this NFA to DFA

following language: L = { wcwR : w is set of all strings over a and b }

automata givenbellow:
(b). (i) Construct a Moore machine that take set of all strings over Alp habet {0, 1} as
input and produce 'A' as output if input end with (10) or produce 'B' as output if input end
with (11) otherwise produce 'C'.
                           (ii) Write the regular expression for L={ anbm:( n + m)  iseven }

L = { anb2n cm :n , m >=0 }
                         (ii) What are ambiguous grammars? Identify whether the following grammar rules are
                               ambiguous or not :
S →  a | abSb | aAb
                                                            A → bS | aAAb

Design a Turing machine which accepts the language L ={ w(a ,b)* : w has
equal number of a’s and b’s }

            X ={ 1 , 10111 , 10}                 Y ={111 ,10 , 0}
         Show that 101111110 is a solution for Post Correspondence Problem.
(ii) Write short noteson the following:
I. Recursive Language and Recursively EnumerableLanguage.
II. Linear Bounded Automata