Conversation

Notices

1. Embed this notice
   Abhiseck Paira :gnu: :gnuhurd: (redstarfish@social.linux.pizza)'s status on Wednesday, 26-Mar-2025 19:00:05 JST Abhiseck Paira :gnu: :gnuhurd:

   I'm reading theory of computation and I've a question which I don't know where to ask but here,

   If DFA M recognizes language A and language B, can we conclude that A = B?

   I'm following 2nd edition of Sipser's book, if that's important.

   • Embed this notice
     Shifty Skip (shiftyskip@social.linux.pizza)'s status on Wednesday, 26-Mar-2025 20:19:46 JST Shifty Skip

     in reply to

     @redstarfish Yes. A DFA either accepts or rejects a given word, and the language it recognises is the set of accepted words.
     Therefore, languages A and B are both "the set of words that are accepted by M".

   • Embed this notice
     Abhiseck Paira :gnu: :gnuhurd: (redstarfish@social.linux.pizza)'s status on Thursday, 27-Mar-2025 01:50:33 JST Abhiseck Paira :gnu: :gnuhurd:

     in reply to

     • Shakil Akhtar 🇸🇦 🇵🇸
     • MortSinyx

     @cnx

     I've found a argument to generate counter examples that show it's not necessary that A = B.

     Let C be a language that's union of two languages A1 and A2. Now we construct a DFA M that recognizes the union language.

     We'll see that M also recognizes A1 and A2 separately, yet clearly A1 is not necessarily equal to C (A1 is a subset of C).

     Similarly, A1 is not equal to A2.

     CC: @shakil_tcs

   • Embed this notice
     MortSinyx (cnx@awkward.place)'s status on Thursday, 27-Mar-2025 01:50:34 JST MortSinyx

     in reply to

     :blobcat_murakamisan_yes: @redstarfish, as both are L(M).

   • Embed this notice
     Shifty Skip (shiftyskip@social.linux.pizza)'s status on Thursday, 27-Mar-2025 02:03:54 JST Shifty Skip

     in reply to

     • Shakil Akhtar 🇸🇦 🇵🇸
     • MortSinyx

     @redstarfish @cnx @shakil_tcs When we say a DFA M "recognizes" a language A, it means M accepts every word in A, and rejects every word not in A.
     This means, in your example, M doesn't recognize A1, because it accepts words that aren't in A1 (those from A2 \ A1).
     M only recognizes the language C and no other.

   • Embed this notice
     Abhiseck Paira :gnu: :gnuhurd: (redstarfish@social.linux.pizza)'s status on Thursday, 27-Mar-2025 14:16:42 JST Abhiseck Paira :gnu: :gnuhurd:

     in reply to

     • Shakil Akhtar 🇸🇦 🇵🇸
     • MortSinyx

     @shakil_tcs
     @cnx

     You are right. Hopcroft's book makes it clear that for M to recognize language A, it must be A = L(M). If some language B exist which is proper subset of A, then M will accept all the of the strings of B and some more that are not in B. In that case, we'll not say that M recognizes B.

     Thanks for your time!

   • Embed this notice
     Shakil Akhtar 🇸🇦 🇵🇸 (shakil_tcs@mstdn.starnix.network)'s status on Thursday, 27-Mar-2025 14:16:43 JST Shakil Akhtar 🇸🇦 🇵🇸

     in reply to

     • MortSinyx

     @redstarfish @cnx M doesn't recognise A1, if A1 =/= A2. It recognises A1 union A2. Unless, you define recognising a language to mean just accepting the words in the language.
     However, the standard definition is accepting every word in the language and rejecting every word not in the language.