Construct the minimum state dfa equivalent to given dfa

Assignment Help Theory of Computation

Reference no: EM133655156

Question 1 Construct the minimum state DFA equivalent to given DFA.

	0	1
q0	q1	q0
q1	q0	q2
q2	q3	q1
q3	q3	q0
q4	q3	q5
q5	q6	q4
q6	q5	q6
q7	q6	q3

Q.1 Design Mealy machine:

If input ends with 100 output x

If input ends with 110 output y

Otherwise o/p z.

Question 2 Explain in detail closure properties of Regular languages.

Q.2 Design FA for following Regular Expression:

a) 10 (0 + 10)* + 1 (1 + 10)* b) 0*1 (0 + 11) + 10

Question 3 What is ambiguous grammar? Find out following CFG is ambiguos

S → aS|∈
S → aS bS

Q.3 a) Find the CFL associated with the CFG given below:
S → aB +bA
A → a|aS|bAA
B → b|bS|aBB

b) Write a grammar for generating string ∑ = (a) containing any number of a's.

Question 4 Construct PDA accepting language consisting of even palindromes string a's and b's.

Q.4 Design PDA for accepting following language

L = {aⁿbⁿ|n≥ 1)

Question 5 What is Turing machine? Design Turing machine for 2's complement of given binary number 01010101.

Q.5 Construct Turing machine for checking well formedness of parenthesis.

Question 6 Explain the applications of CFG in syntax analyzer phase of compiler with suitable example.

Reference no: EM133655156

Questions Cloud

Examine different periods of policing : Examine different periods of policing and discuss their main strengths and weaknesses.

Continued commitment and shared pursuit of change : You mentioned that a truly inclusive and equitable future of policing can only be achieved through continued commitment and a shared pursuit of change.

Provide an overview of the strengths of each channel choice : Provide an overview of the strengths and weaknesses of each channel choice. Support each channel choice with observations from the company profile.

Where have you found unpublished or grey evidence : Where have you found unpublished or grey evidence? In what way have you used this type of evidence?

Construct the minimum state dfa equivalent to given dfa : Explain in detail closure properties of Regular languages and Construct the minimum state DFA equivalent to given DFA

What level of output manager of redstone choose to produce : What level of output should the manager of Redstone choose to produce? Explain your choice in at least 100 words. Should the firm shut down in the short-run?

Evaluate the pattern of vehicle burglaries in community : A university professor initiates a research project designed to evaluate the pattern of vehicle burglaries in a community.

Capture accurate data involving juvenile delinquency : Pretend you are a researcher trying to determine the best way to capture accurate data involving juvenile delinquency

Prosecutors spend most of their time working directly : Prosecutors spend most of their time working directly with other members of the courtroom work group.

User Account

All Pages