Construct a regular expression

Assignment Help Theory of Computation

Reference no: EM132163919

Q1. For the NFA N given below, using the powerset construction, construct a DFA M that accepts the same language accepted by N. Do not include states which are not reachable from the initial state of your DFA. Do not simplify your DFA and for each state in the constructed DFA, label it with a subset of all states of N in the usual way.

Q2. Consider the following NFA:

The goal is to construct a regular expression the accepts the same language as the above NFA.

(a) Draw the NFA after adding the new i and the a states as stated in the initialization of the algorithm to compute the regular expression.

(b) Continuing (a), draw the NFA (with regular expressions as labels) after you remove qo.

(d) Continuing (c), draw the NFA (with regular expressions as labels) after you remove q2.

(e) Continuing (d), draw the NFA (with regular expressions as labels) after you remove q3.

(f) Continuing (e), draw the NFA (with regular expressions as labels) after you remove q4.

Q3. Let L, L' be two languages over Σ Define
T(L, L') = {c₁c'₁c₂c'₂....c_nc_n' | c_i ∈ Σ, C'_i ∈ E, c_i' ∈ Σ, c₁, c₂, c_n c_n, ∈ L, and c'₁c'₂....c'_n ∈ L'}

Prove that if L, L' are regular, then T(L, L') is also regular. This means that you have to assume L has a DFA say (E, Q, q₀, F, δ) and L' has a DFA say (E, Q, q₀, F, δ), you then construct a DFA for T(L, L'). To show that you understand the question, you are advised to provide one or two specific examples for L and L' and then state what you get when you construct T(L.L') using your method.

NOTE: The style of this question and the expected answer is similar to other closed operator construction from class. For instance we have the complement construction, the cross product construction and also the powerset construction.

Reference no: EM132163919

Questions Cloud

Calculate the schedule variance-schedule performance index : Calculate the schedule variance, schedule performance index, and cost performance index for the project to date.

What information is provided under the vulnerabilities tab : Using a web browser, visit securityfocus website, what is Bugtraq, and how would it be useful? what additional information is provided under the Vulnerabilities

Describe three most common performance management systems : Describe the three most common performance management systems that can be used for a companies strategic growth.

Identify and define virtual worker roles : Assess whether or not the Water Cube project management team achieved the selected enhancers. Identify specific examples to justify your assessment.

Construct a regular expression : Construct a regular expression the accepts the same language as the above NFA - cross product construction and also the powerset construction

What performance standards and expectations : What performance standards and expectations does the organization need to set for our expats abroad?

Fiedler contingency theory-house path-goal leadership theory : Discuss how you would apply Fiedler's Contingency Theory, House's Path-Goal Leadership Theory,

Evaluation and analysis supported with concepts described : The research study can, for example, include the following: Evaluation & Analysis, supported with concepts described in the course and outside research

Does it make sense to use the tit-for-tat rule when dealing : Does it make sense to use the "tit-for-tat" rule when dealing with personal friends and family members?

User Account

All Pages