1

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?

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
redundant6939
  • 153
  • 3
  • 5
  • 16

2 Answers2

1

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.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • 1
    The RE for L1 is just `(a+b)*`. – n. m. could be an AI Oct 02 '13 at 10:00
  • 1
    @n.m. To include `^` RE should be `(a + b)*a(a + b)*b(a + b)* + ^`, but no `(a + b)*` generates = `aaaa..` or `bbb..` so not a RE for L1. – Grijesh Chauhan Oct 02 '13 at 10:02
  • I'm afraid I don't understand your argument. Is ^ in the language? Does x* generate ^? Does your RE generate ^? – n. m. could be an AI Oct 02 '13 at 10:11
  • @n.m. `^` (is nul) yes `^` string can be included in language `L1` where both prefix string `x` and suffix string `y` are `^` and constant `numberOf(a) == numberOf(b) == 0`. But a string consists of only symbol `a` or symbol `b` can't be broken into `x`, `y` such that `numberOf(a) == numberOf(b)` because at-lest one will be zero other non-zero. No my RE in answer doesn't generate `^`. – Grijesh Chauhan Oct 02 '13 at 10:14
  • "But a string consists of only symbol a or symbol b can't be broken into x, y" - why, of course it can, s=s^=^s, one of them will fit. – n. m. could be an AI Oct 02 '13 at 10:20
  • @n.m. Yes that is the reason that I said `(a + b)*` is not the RE for `L1` (what you commented). In my RE I always add at-least one `a` and one `b`... – Grijesh Chauhan Oct 02 '13 at 18:41
0

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.

sanjay jonnakuti
  • 1