CODEWITHSUNDEEP
regular-languageautomatadfanfa
Asher Castro
Asher Castro

Reputation: 11

Prove that the following language is regular:

Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.

Prove that the following language is regular, by making an appropriate NFA for it:

𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎𝑛𝜎𝑛′ |𝜎1𝜎2…𝜎𝑛∈𝐿1,𝜎1′𝜎2′…𝜎𝑛′ ∈𝐿2} (Meaning, the language of all words in which the letters on the even positions (starting from 0) are from L1 and the letters on the odd positions are from L2.

Would appreciate help with that. Thank you.

Upvotes: 0

Views: 263

Answers (1)

Patrick87
Patrick87

Reputation: 28312

Consider the following automaton:

  • alphabet Σ
  • set of states (Q x P) union (P x Q)
  • initial state (q0, p0)
  • final states (f1, f2) where f1 and f2 are in F1 and F2, respectively
  • transition function that takes (q, p) to (p, q') on symbol s if 𝛿1 takes q to q' on s, and which takes (p, q) to (q, p') on symbol s if A2 takes p to p' on symbol s.

Suppose that you have a word w in L3. Does our machine accept it? The sequence 𝜎1, 𝜎2, …, 𝜎n will cause the first component of the state in which the automaton arrives to be the same as the state A1 would have arrived in had A1 processed just this sequence. Since L3 says this sequence in w is a word in L1, the state should have been accepting in A1 and so the first component is in F1. Similarly, the sequence 𝜎1', 𝜎2', …, 𝜎n' is a string in L2 and so the state it arrives at is accepting. Thus, the state reached by this NFA is of the form (f1, f2) and thus the string is accepted, as it must be. We have just argued that the NFA accepts at least the strings in this language. What remains is to argue that it does not accept anything else.

Fortunately, the remainder of the argument is straightforward, and we probably could have done it at the same time as we did the above one. It follows the same format. Suppose our NFA arrives at one of the accepting states. Then it's of the form (f1, f2). That means we saw an even-length string where the odd-index symbols considered together led to f1 in A1 and the even-index symbols led to f2 in A2. But that means the sequences were accepting in their respective automata and so the string that led us to the accepting state in our machine must be a word in L3. We have just argued that the NFA accepts at most the strings in this language.

Since our machine accepts at least the strings we need, and at most the strings we need, it follows that it accepts exactly the strings we need.

Upvotes: 1

Related Questions