Build a deterministic pushdown automata

Assignment Help Theory of Computation

Reference no: EM133124117

CSC 420 Theory of Computation - University of Tabuk

Question 1: Give DFAs for the following languages over the alphabet is Σ = {a, b}

1) The language L(RE = b*a(ab)*b).

2) The language {w ∈ Σ* | w starts with ab}.

Question 2:

Convert the following CFG into an equivalent CFG in Chomsky Normal Form (CNF) over the

Σ = {a, b}.

S → aS |bbX

X → aaX| bY | ε

Y → aX

Question 3:

Consider the following CFG over {0,1}:
S → 0S | 0X
X → 11X | ε

1) What is the regular expression (RE) accepted by this CFG?

2) Show that whether this CFG is ambiguous or not:

3) Show that whether the word "01111" is accepted or not by this CFG:

4) Convert this CFG into PDA.

Question 4: Consider the following language:

L1 = L(re=0100*)

a) Build a deterministic pushdown automata (PDA) that recognizes this language L1 over the Σ = {0, 1}.

b) Build a Turing Machine(TM) that recognizes this language L1 over the Σ = {0, 1}.

Reference no: EM133124117

Questions Cloud

Licensing requirements for employees and employers : Outline 2 methods to update and maintain information on relevant laws and licensing requirements for employees and employers.

What is the volume required to breakeven : Longhorn Clinic currently provides 1,000 visits per year at a price of $40 per visit. What is the volume required to breakeven

Effective interest rate of investment : 1) The effective interest rate of investment is 10.04% per annum. Convert this to a nominal rate, compounded quarterly.

Process for developing information security program : Describe the primary goals and process for developing an information security program in your organization or an organization with which you are familiar.

Build a deterministic pushdown automata : What is the regular expression (RE) accepted by this CFG - Build a deterministic pushdown automata (PDA) that recognizes this language

Find the solution that gives the maximum profit : A plastic parts supplier produces two types of plastic parts used for electronics. Type 1 requires 1 hour of labor and 2 hours of machine time.

Organization about cloud computing : Find the details of the project and pick any one of the organization about Cloud Computing. Discuss challenges the organization had that limited profitability

How wages are determined : Labor markets are an important concept to understand in terms of how wages are determined. Explain how COVID has impacted wages in our economy.

Journalize the entries to record the transactions : Journalize the entries to record transactions. Refer to the Chart of Accounts for exact wording of account titles. Assume 360-day year when calculating interest

User Account

All Pages