Question

Let S = {<M> | M is a DFA that accepts wR whenever it accepts w}. Show that S is decidable. Let S = {<M> | M is a DFA that accepts wR whenever it accepts w}. Show that S is decidable.

Answer #1

To shown "S" is decidable, Construct Decider "D" for S as follows :-

Let (T) be the Turning Machine(TM) that makes a decision Equivalent to DFA (denoted as ):

D = On Input <M> ,

- Construct a Non-deterministic Finite Automaton(NFA)
**M′**such that L(**M′**) = { | W ∈ L(M) } - Convert
**M'**into an equal Deterministic Finite Automaton(DFA)**M''** - Use T to compare/evaluate L(
**M''**) andL(**M**) - If L(
**M''**) = L(**M**), accept it. else, reject it.

In the above Turning Machine (TM),

Step 1 may be achieved via way of means of converting
**M** into **M'** in finite steps.

The concept is to

(i) opposite the directions of all transition arrows in
**M**

(ii) create a new state **q'** in
**M'**, and connects **q'** to every
unique very last states of **M** with ε-transitions,
and

(iii) make the unique begin state of **M** final
state of **M'**.

It is simple to check that L(**M'**) =
| W ∈ L(**M''**) > w∈ L(**M**).

Also, both Step two and Step three may be achieved in finite steps

D runs in finite steps and is for this reason a decider

design a DFA for L, where E = {0,1} and L = {w|(# of 0's in w)
satisfies 3i+2, i>= 0}

ATM = {<M, w> | M accepts w| HALT TM= {<M,w | M halts
on w|
Can you describe any TM M and its input w, so that M on w goes
to q-accept, but M on w does not halt? Can you describe any TM M
and its input w, so that M on w does not go to q-accept, but M on w
does halt?
Can you describe any TM M and its input w, if
possible, that is...

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 !

Let S, U, and W be subspaces of a vector space V, where U ⊆ W.
Show that U + (W ∩ S) = W ∩ (U + S)

The circumferential velocities in a free vortex and forced
vortex , respectively, u 0=C/r and uo=wr, where r is the radius in
meter , velocity is in m/s, C is 4 m^2/s, and w=1.0 rad/s. for both
cases , calculate the circulation around a circular path with a
radius of 1m and center at (0,0) .Are these inviscid flows? note
that ur=0 ?

Let W be an inner product space and v1,...,vn a basis of V. Show
that〈S, T 〉 = 〈Sv1, T v1〉 + . . . + 〈Svn, T vn〉
for S,T ∈ L(V,W) is an inner product on L(V,W).
Let S ∈ L(R^2) be given by S(x1, x2) = (x1 + x2, x2) and let I ∈
L(R^2) be the identity operator. Using the inner product defined in
problem 1 for the standard basis and the dot product, compute 〈S,...

Let W be the work (against gravity) required to build
a pyramid with height 4m, a square base of side length 4m, density
of 600kg/m^3, and gravity 9.8m/s^2. Show that W = 1003520J

Let S={u,v,w}S={u,v,w} be a linearly independent set in a vector
space V. Prove that the set S′={3u−w,v+w,−2w}S′={3u−w,v+w,−2w} is
also a linearly independent set in V.

Let V = R^3 and let W ⊂ V be defined by W = span{(1, 1, 1),(2,
1, 0)}. Show that W is a plane containing the origin, and find the
equation of W.

let T:V to W be a linear transdormation of vector
space V and W and let B=(v1,v2,...,vn) be a basis for V. Show that
if (Tv1,Tv2,...,Tvn) is linearly independent, thenT is
injecfive.

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 25 minutes ago

asked 37 minutes ago

asked 42 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago