Question

Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.

Short answer

Answer:

The problem expressed as a language as follows,

$E{Q}_{DFA,REX}=\{<F,R>|FisaDFA,RisaregularExpression,L\left(F\right)=L\left(R\right)\}$

The above language is decidable.

Step-by-step solution

Explain decidability.

The automata and the grammars helps to decide the outcome of the undecidable problems. The Deterministic Finite Automata determines the state of the string given as input.

Express this problem as a language and show that it is decidable.

Consider the given Context-free language

$E{Q}_{DFA,REX}=\{<F,R>|FisaDFA,RisregularExpression,L\left(F\right)=L\left(R\right)\}.$Consider the

following Turing Machine M decides $E{Q}_{DFA.REX}$. Construct the mapping function

$f:{\in }^{*}\to {\in }^{*}$for the inputs,

$M={"}^{}$On inputs $<A>$where A is a DFA

1. $f(<F,R>)=<F,F_R>$, where $F_R$is the Deterministic Finite Automata Constructed from the

regular expression R, such that $L\left(F_R\right)=L\left(R\right)$

2. L(F) = L (R), if and only if L (F) = $=L\left(F_R\right),$

Thus $E{Q}_{DFA,REX}{\le }_{m}E{Q}_{DFA}$

Therefore, the language

$E{Q}_{DFA,REX}=\{<F,R>|FisaDFA,RisregularExpression,L\left(F\right)=L\left(R\right)\}$is decible