Question

6. Prove or disprove the following conjecture. If M = (Q, Σ, δ, q0, F) is...

6. Prove or disprove the following conjecture. If M = (Q, Σ, δ, q0, F) is a minimal dfa for a regular language L, then M̂ = (Q, Σ, δ, q0, Q − F) is a minimal dfa for L¯.

help me plz...

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Answer:

  • Lets say that is not a minimal DFA of .
  • Then there must be another DFA P which accepts .
  • Since is not minimal , P will have lesser number of states than .
  • We can swap the final states to non-final and non-final to final for P so that the resultant DFA accepts which is equivalent to L.
  • So now recognizes L.
  • we know that and P have the same number of states.
  • And and M also have the same number of states.
  • We assumed that P will have the lesser number of states than .
  • Then we can say that will have lesser states than M.
  • But recognizes L , which is a contradiction to our assumption. So M is a minimal DFA for L and is minimal DFA for .
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let M be defined as follows: M = ({q0, q1, q2, q3}, Σ = {a, b},...
Let M be defined as follows: M = ({q0, q1, q2, q3}, Σ = {a, b}, ∆, s = q0, F = {q2}) and ∆ = {(q0, a, q1), (q1, b, q0), (q1, b, q2), (q2, a, q0)} 1. (2pts) Draw the diagram of M 2. (13pts) Evaluate all relevant steps of the general method of transformation the NDFA M defined above into an equivalent DFA M0 . Do it in the following STAGES. STAGE 1 (3pts) For all q...
Let s and p be two particular strings over an alphabet Σ. Prove that the following...
Let s and p be two particular strings over an alphabet Σ. Prove that the following language M = {w ∈ Σ ∗ | w contains u as a substring but does not contain v as a substring} is regular. plz provide DFA and also simplified the DFA thx !
1. Consider the deterministic finite automaton (K, Σ, δ, s, F) where K = {p, q,...
1. Consider the deterministic finite automaton (K, Σ, δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, s = p, F = {q} and δ is given by the following chart: x       y     δ(x, y) p       a         q p       b         q p       c          r q       a         r q       b         p q       c         p r        a          r r        b          r r        c           r Find a regular expression for the language recognized by this automaton
For all Questions below do the following. 1. 1pt Draw the State Diagram of M. 2....
For all Questions below do the following. 1. 1pt Draw the State Diagram of M. 2. 2pt Determine whether M is / is not a finite state automata and determine whether M is deterministic or non-deterministic, if applicable. 3. 3pts Describe L(M) (1pt) and write a a regular expression (2pts) that defines it. Q1 M = (K, Σ, s, ∆, F ) for K = {q0} = F, s = q0, Σ = ∅, ∆ = ∅. Q2 M =...
Part IV: All of the following arguments are VALID. Prove the validity of each using NATURAL...
Part IV: All of the following arguments are VALID. Prove the validity of each using NATURAL DEDUCTION. 1) 1. H É I 2. U v ~I 3. ~U 4. H v S                                               / S 2) 1. (I × E) É (F É Y) 2. Y É ~C 3. I × E                                                 / F É ~C 3) 1. L v O 2. (F v C) É B 3. L É F 4. O É C                                              / B 4) 1. K ×...
Consider permutations of the 26-character lowercase alphabet Σ={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}. In how many of these permutations do a,b,c...
Consider permutations of the 26-character lowercase alphabet Σ={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}. In how many of these permutations do a,b,c occur consecutively and in that order? In how many of these permutations does a appear before b and b appear before c?
A firm produces X using the following production function: Q = F(K,L) = 32K0.76L0.24. K=6 units....
A firm produces X using the following production function: Q = F(K,L) = 32K0.76L0.24. K=6 units. If the firm can sell each unit X at $22.20 and can hire labor at $16.00 per unit. Answer the below questions with the information provided. The total profits when the firm uses optimal labor is? How many workers the firm will hire in order to maximize profits? How many units of X the firm will produce in order to maximize profits?
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT