Use the result of the previous question httpswwwcheggcomhome

Use the result of the previous question (https://www.chegg.com/homework-help/questions-and-answers/given-two-dfas-b-show-construct-dfa-c-l-c-l-l-b--prove-construction-works-proving-statemen-q18873688) to show that the following language is decidable. Just give the construction (step 1 in the lecture slides), as you have done the bulk of the correctness proof (step 2 in the lecture slides) in the previous question.

L = {R, S | R and S are regular expressions and L(R) L(S)}

Solution

If L(R) L(S) then L(R) L(S) = L(R).

Input: <R, S> for some regex R and some regex S

Output: ACCEPT if L(R) L(S), and REJECT otherwise

Algorithm:
- L(R) and L(S) are regular, and so L(R) L(S) is also regular (Intersection is closed for Regular languages)
- Construct a DFA M that recognizes L(R) L(S)
- Let MR be a DFA for regular expression L(R).
- We know Equivalence property (EQDFA) is decidable for DFA.
Run the Decider for EQDFA on <M, MR>
o If <M, MR> is in EQDFA, then ACCEPT
o Else REJECT