CODEWITHSUNDEEP
computer-scienceautomata
EndHD
EndHD

Reputation: 11

Push down automata design for language L = {w ∈ {a, b}∗ | (w = w^R) and number of a’s = number of b’s}

w = w^R means the reverse of w is the same as w

I am trying to create a push down automaton for L = {w ∈ {a, b}∗ | (w = w^R) and number of a’s = number of b’s}.

I have the PDA for equal number of a's and b's and PDA for a palindrome. Is trying to combine them the right step?

Upvotes: 1

Views: 1913

Answers (1)

Patrick87
Patrick87

Reputation: 28322

We will prove this language is non context-free using the pumping lemma for context-free languages. Assume the language were context-free. Then, by the pumping lemma for context-free languages, any word w in the language could be written w = uvxyz where the following hold:

  1. |vxy| <= p
  2. |vy| > 0
  3. for any natural number k, u(v^k)x(y^k)z is also in the language

Consider the string (a^p)(b^1.5p)(a^p)(b^1.5p)(a^p) in the language (it has the same number of a as b and it's the same forward as backward). There are various cases for the substring vxy:

  1. vxy consists entirely of a from the first segment. Pumping this results in a string which cannot be a palindrome since the first and last segments of a cannot have the same length anymore.
  2. vxy consists of a and b from the first two segments. Pumping changes the first two but not the last two segments so it can't produce a palindrome.
  3. vxy consists of b from the second segment. Pumping this results in a string which cannot be a palindrome.
  4. vxy consists of b from the second segment and a from the middle. Again, this cannot produce a palindrome since you get fewer b on the left than the right.
  5. vxy consists of a only from the middle. the result of pumping might well be a palindrome but it cannot possible have equal numbers of both a and b now.

All remaining cases are perfectly symmetric to the ones already covered. This means there is no choice for vxy such that pumping gives us strings in the language. This is a contradiction, so our assumption about the language being context-free was wrong.

We relied on |vxy| <= p for this to keep the number of cases small and make pumping fail. If we picked the middle segment of a to have length less than p - 2, this wouldn't have worked since we could have chosen v = (b^n)(a^n) and y = (a^n)(b^n) and it would have pumped just fine.

Upvotes: 1

Related Questions