Machine Diagram

07-12-17 cheapnisha 0 comment

Machine Diagram

Section A

  • Let L € {a, b} * be the language corresponding to the regular expression

bba(ab)*+(ab+ba*b)*ba

  • Generate the complete CFG for this and convert to CNF
  • Show the NFA and DFA
  • Show that the CFG given by

Sà  a | Sa | bSS | SSb | SbS

Is ambiguous.

  • Describe the “halting problem” for Turing machines.

Prove or disprove that halting problem is undecidable

  • Consider the language of simple palindromes (with a ‘c’ in the middle position)

SP = { XCX | X € {a , b}*}

  • Machine DiagramWhat is the least functional FA that can accept this language? Why?
  • Construct the transition table or the state diagram.
  • Process the following through the FA and indicate what happens – abcba ,acab , and abc
  • Let L be the language of balanced strings of parentheses, just as they would appear in legal algebraic expression.
  • Using [ ] as the symbols for the parentheses, show the CFG with its productions.
  • Show the PDA for part ( a ).
  • Show the computations trace for [ [ ] [ ] ].
  • For the language specified by

{ aibjck  | i>=  j or i>= k }

Show that it is a CFL but it is complement is not.

  • Consider the following two language specifications

L1 = AnBnCn = { anbncn | n belongs to N the set of natural numbers }

L2 = L = { xcx | x € [ a , b}* }

  • What kind of FA is required to accept the two language and why?
  • Show the formal definition for the FA identified in part ( a ) for L1.
  • Show the transition table for part ( b ).

Section B

  • Consider two language L1 and L2 defined as follows:

L1 = { x € (a , b) | Where x contains the substring ab }

L2 = { x € (a , b) | Where x contains the substring bba }

  • Show the state diagram for L1 and L2.
  • Show the optimal FA accepting L1 U L2.
  • Design a TM and show the machine diagram that accept the language defined by:

L = { aibaj | 0 <= i< j }

  • PCP
  • Describe post’s correspondence problem.
  • Is post’s correspondence problem solvable? Explain.
  • Given the following:

A = ( a , abaaa , ab ) and B = ( aaa , ab , b )

As two strings, provide a solution to PCP.