Question

The language {w| w is the set of all balanced parenthesis} is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

Answer 1

Answer on Question#38640 – Math - Other

We have 3 types of parentheses: round brackets: (), square brackets: [], and curly brackets: {}.balanced parentheses require every opening parenthesis to be closed in the reverse order opened. For example ‘([])’ is balanced but ‘($])’ is not.

By the Chomsky–Schützenberger theorem, any context-free language is a homomorphic image of the intersection of some regular language with a homomorphic preimage of the Dyck language on two parentheses. And the Dyck language (of well-balanced bracket pairs) is non-linear, context-free language.

So the correct answer is B.