CODEWITHSUNDEEP
context-free-grammardiscrete-mathematicsregular-languagecontext-free-language
user5717696
user5717696

Reputation: 5

classify as regular, context free, or other

Could someone answer these questions and dumb it down for me please, I am not fully grasping the ideas. I am overall confused at things like "what exactly are terminals?""What does w stand for?"

but as for the real question here they are, please classify as regular, context-free, or other.

a) {a^nb^na^n} ∩ # of a's is even.
b)(a^nb^n) ∪ palindrome
c)a^n+m b^m a^2n

Please classify and explain.

Upvotes: 0

Views: 942

Answers (1)

Patrick87
Patrick87

Reputation: 28292

{a^nb^na^n} ∩ # of a's is even.

Every string in {a^n b^n a^n} has 2n a's, an even number, so the intersection does not further restrict the language. The intersection is equal to {a^n b^n a^n}. This is similar to one of the canonical context-sensitive languages a^n b^n c^n. We can show that language is not context free using the pumping lemma for context free languages. Then, note that if a^n b^n a^n were context free, you'd expect (a+c)^n b^n (a+c)^n to be as well, since any PDA for the former can just treat a and c the same and accept the latter. However, the intersection of a CFL and a RL must be a CFL and (a+c)^n b^n (a+c)^n intersect aabbcc* is a^n b^n c^n (n > 0), which is not context free, a contradiction. OTHER.

(a^nb^n) ∪ palindrome

Assume this were regular. Then the intersection with the regular language of all odd-length strings would be regular. All odd length strings in the above union are odd-length palindromes. Odd length palindromes are not regular, a contradiction. Now, a^n b^n is given by the CFG S := aSb | "", and palindromes are a canonical example of context-free languages, and the union of CFLs is also a CFL, so this is CONTEXT FREE.

a^(n+m) b^(m) a^(2n)

We can rewrite this as a^n a^m b^m a^2n. Then we see this is CONTEXT FREE since a CFG is S := Q; Q := aQaa | "" | R; R := aRb | "". It can be shown not to be regular by the pumping lemma for regular languages.

Upvotes: 1

Related Questions