'''Originally Posted By: jnewth''' <br>For each of the following languages, either give an algorithm to show its decidable or prove that its not: ALL_DFA, EQ_REX, EQ_CFG.<br><br><br>a) ALL_DFA is decidable. ALL_DFA is the language consisting of all encodings of DFAs having the property that they accept all strings over their alphabet. <br><br>Examining this slide http://www.cs.sjsu.edu/faculty/pollett/154.1.11s/Lec20042011.html#%284%29 tells us that E_DFA is decidable, meaning, given an encoding for a DFA we have a decider D that will examine this encoding and tell us whether or not the language accepted by this DFA is empty or not. <br><br>We also know that given a DFA we can construct a machine that will accept the complement of the language accepted by the DFA. DFA is closed under complement, a result shown in class and in the book.<br><br>To prove ALL_DFA is decidable we construct a machine that works in the following manner:<br><br>1. Construct DFA&rsquo; the complement of DFA.<br>2. Use D, our decider for E_DFA on DFA&rsquo;. If DFA&rsquo; is empty, we know its complement (the original DFA) contains all possible strings. If the language of DFA&rsquo; is not empty, then we know that there exists at least one string that is not included in the language of the original DFA. Therefore ALL_DFA is decidable.<br><br>b) EQ_REX is decidable. EQ_REX is the set of strings of the form where R1 and R2 are both regular expressions and R1 and R2 each generate the same language.<br><br>Given a regular expression R we can construct the DFA that accepts the same language that R generates (shown in class). We also know that DFAs are closed under union, complement, and intersection (proved in class and in the book), so given two DFAs we can construct a DFA3 that accepts the symmetric difference (see page 171 of the book) of the two DFAs that accepts only the strings that are accepted by EITHER DFA1 OR DFA2 but reject those strings accepted by both. <br><br>We know from the slide that E_DFA is decidable, meaning we can construct a machine that given a DFA will say if that DFA accepts no strings. We use this decider on DFA3. If DFA3 is empty, it means that DFA1 and DFA2 accept all the same strings. If DFA1 and DFA2 accept all the same strings, they are equivalent, and so are the regular expressions that they represent. Therefore EQ_REX is decidable.<br><br>c) EQ_CFG is undecidable. EQ_CFG is the set of all encodings of the form where CFG1 and CFG2 generate the same strings (ie, are equivalent).<br><br>For this proof, please recall that ALL_CFG is the set of all encodings of CFGs that have the property of generating all strings. From the book page 201 we know ALL_CFG is undecidable. <br><br>We use proof by contradiction. We assume there is a decider for EQ_CFG. If we did have a decider for EQ_CFG, then we could also construct a decider for ALL_CFG by first creating a CFG3 that generated all strings. If we wanted to decide if some other CFG4 was in ALL_CFG, we could use our decider for EQ_CFG on . Thus, assuming EQ_CFG is decidable produces a contradiction.

-- Practice Final #5

'''Originally Posted By: kaurm''' Meena Kaur<br>Vinesh Thakur<br>Nas<br><br>We worked on this problem.