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}*}

• What 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

Machine Diagram

{ 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.