4

Given the languages

L1={anb2m|n,m≥1}
L2={anb3n|n≥0}

L = L1 ∩ L2

I know that L1 is regular language and L2 can be represented by a PDA.

But I don't understand the answer which states that L is {a2nb6n|n≥1}. How was this solution computed?

rici
  • 234,347
  • 28
  • 237
  • 341
totoro
  • 109
  • 2
  • 9
  • Possible duplicate of [What is the intersection of two languages with different alphabets?](http://stackoverflow.com/questions/15213955/what-is-the-intersection-of-two-languages-with-different-alphabets) – veganaiZe Feb 16 '17 at 18:08
  • @rici that is exaclty what i don't understand about it, `L` is basically the solution provided – totoro Feb 17 '17 at 07:58
  • @totoro: OK, I tried to edit your question to make it clearer what your point of confusion was. Questions like this really should be asked on http://cs.stackexchange.com/, since they really have nothing to do with programming. However, be aware that your question will not be well-received there unless you make some attempt to show your work. – rici Feb 17 '17 at 15:09

1 Answers1

8

A language is just a set (of valid strings), so what we have here is really just a simple problem in integer arithmetic. It's only necessary to remove the elegant costume of formal languages to arrive at the essence of the problem.

Both sets L1 and L2 are subsets of {acount(a)bcount(b)|j,k≥0}; that is, they consist of some number of as followed by some number of bs. The condition for L1 restricts count(b) to be a positive even number, since it must be 2m for some integer m≥1. The condition for L2 restricts count(b) to be exactly 3×count(a).

Now, the intersection of two sets defined with predicates is the set of elements such that both predicates are true. So count(b) must be both divisible by 2 and by 3, which means that it must be divisible by 6; in other words, it must be 6n for some positive integer n. And that means that count(a) must be 2n since there are exactly three times as many bs. That gives you the provided answer.

Like L2, L is not regular, but it can be implemented with a very similar PDA.

rici
  • 234,347
  • 28
  • 237
  • 341