Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
edited body
Source Link
dkaeae
  • 5.1k
  • 1
  • 17
  • 31

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can iI just use the given $M$ as a decider?

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
  1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  2. Recursively: mark states that can be obtained within a finite $δ$
operations from any marked states. 
  1. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can i just use the given $M$ as a decider?

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
  1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  2. Recursively: mark states that can be obtained within a finite $δ$
operations from any marked states. 
  1. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can I just use the given $M$ as a decider?

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
  1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  2. Recursively: mark states that can be obtained within a finite $δ$
operations from any marked states. 
  1. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

Improve TeX, presentation, retag
Source Link
dkaeae
  • 5.1k
  • 1
  • 17
  • 31

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several timetimes

iI am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$  (not using the proof in siplersSipser's book "Introduction to the Theory of Computation").

canCan i just use the given M$M$ as a decider?

M="on input<B,w>, where B is a DFA and w is an empty string($L(w)=\emptyset$):

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
  1. mark the start of the DFA as $q_0$.
  2. simulate B on input w a finite number of times: a)firstFirst check if the encoding is correct, if $L(w)=\emptyset$, if not - reject. b)recursively
  3. Recursively:mark mark states that can be obtained within a finite $δ$ operations from any marked states. 3.if no accept state marked - accept. else, reject.
operations from any marked states. 
  1. If no accept state marked - accept. else, reject."

have i done itIs this correct? if not, how should it be done?

definitionsDefinitions:$A_{DFA}\:=\:\left\{<B,w> |\:B\:is\:a\:DFA\:that\:accepts\:input\:string\:w\right\}$

$E_{DFA}\:=\:\left\{<A> |\:A\:is\:a\:DFA\:and\:L\left(A\right)\:=\:\varnothing \right\}$ $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

emphasisEmphasis: iI am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times  (finite), so iI thought the correct thing would be to use the input w$w$ as empty set.

would appreciate further assistance.

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several time

i am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$(not using the proof in siplers book).

can i just use the given M as a decider?

M="on input<B,w>, where B is a DFA and w is an empty string($L(w)=\emptyset$):

  1. mark the start of the DFA as $q_0$.
  2. simulate B on input w a finite number of times: a)first check if the encoding is correct, if $L(w)=\emptyset$, if not - reject. b)recursively:mark states that can be obtained within a finite $δ$ operations from any marked states. 3.if no accept state marked - accept. else, reject.

have i done it correct? if not, how should it be done?

definitions:$A_{DFA}\:=\:\left\{<B,w> |\:B\:is\:a\:DFA\:that\:accepts\:input\:string\:w\right\}$

$E_{DFA}\:=\:\left\{<A> |\:A\:is\:a\:DFA\:and\:L\left(A\right)\:=\:\varnothing \right\}$

emphasis: i am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times(finite), so i thought the correct thing would be to use the input w as empty set.

would appreciate further assistance.

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$  (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can i just use the given $M$ as a decider?

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
  1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  2. Recursively: mark states that can be obtained within a finite $δ$
operations from any marked states. 
  1. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times  (finite), so I thought the correct thing would be to use the input $w$ as empty set.

Source Link

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several time

i am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$(not using the proof in siplers book).

can i just use the given M as a decider?

M="on input<B,w>, where B is a DFA and w is an empty string($L(w)=\emptyset$):

  1. mark the start of the DFA as $q_0$.
  2. simulate B on input w a finite number of times: a)first check if the encoding is correct, if $L(w)=\emptyset$, if not - reject. b)recursively:mark states that can be obtained within a finite $δ$ operations from any marked states. 3.if no accept state marked - accept. else, reject.

have i done it correct? if not, how should it be done?

definitions:$A_{DFA}\:=\:\left\{<B,w> |\:B\:is\:a\:DFA\:that\:accepts\:input\:string\:w\right\}$

$E_{DFA}\:=\:\left\{<A> |\:A\:is\:a\:DFA\:and\:L\left(A\right)\:=\:\varnothing \right\}$

emphasis: i am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times(finite), so i thought the correct thing would be to use the input w as empty set.

would appreciate further assistance.