CODEWITHSUNDEEP
regular-languagedfa
redundant6939
redundant6939

Reputation: 153

Are those two regular languages the same?

Given an alphabet of {a, b} where Na denotes the number of occurrences of a, and Nb the number of occurrences of b:

  1. L1 = {xy | Na(x) = Nb(y)}
  2. L2 = {w | Na(w) and Nb(w) are even number}

Wouldn't a single DFA with four states and using mod be able to accept both languages?

Upvotes: 1

Views: 1263

Answers (2)

sanjay jonnakuti
sanjay jonnakuti

Reputation: 1

Both the languages L1 = {xy | Na(x) = Nb(y)} and L2 = {w | Na(w) and Nb(w) are even number}are different so we cannot draw a single DFA for both languages. For Language L1 : A = {xy | Na(x) = Nb(y)} is a regular language. Regular expression for this language is:

(a + b)*a(a + b)b(a + b)
Language L2 : A = {w | Na(w) and Nb(w) are even number} is also a regular language. Regular expression for this language is:

((a + b(aa)ab)(bb)(ba(aa)ab(bb))*a + (b + a(bb)ba)(aa)(ab(bb)ba(aa))b) Both languages are not equal because there are some strings in language L1 which doesnt belong to language L2. ab is a string in L1 but doesn't not consist of even number of a and b hence doesn't belongs to language L2.

As Both languages are different,single DFA cannot be constructed that accepts both the languages.

Upvotes: 0

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

No, because both languages are different so you can't draw single DFA for both languages.

An automaton uniquely defined a language, but yes of-course for a language more than one automata are possible called 'equivalent automata'.

Language L1 = A = {xy | Na(x) = Nb(y)} is a regular language. Regular expression for this language is: 

(a + b)*a(a + b)*b(a + b)*  +  ^

To understand this language and regular expression read: "Show that the following set over {a, b} is regular".

Language L2 = A = {w | Na(w) and Nb(w) are even number} is also a regular language. Regular expression for this language is:

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)*

To understand this language and regular expression read: "Need Regular Expression for Finite Automata".

But both languages are not equal because there are some strings in language L1 those are not belongs to language L2 e.g. ab is a string in L1 but doesn't not consist of even number of a and b hence doesn't belongs to language L2.

Note: Language L2 is either not a subset of language L1, because in L2 a strings of even length and single symbol is possible like aa, aaaa, bb, bbbb but these strings are not member in L1.

Both languages are different hence single DFA is not possible for both languages.

Upvotes: 1

Related Questions