Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses.

Clearly x(), (xy) , ()()xxx, ((xx)) are accepted. BUT

My question is, is a string with no parentheses considered as having balanced parentheses? For example are: y, xxyy, xyxyxxx accepted?

And then also what about an empty String?


This is what formal definitions are for...

That said, it makes the most sense to allow no parentheses. Roughly speaking, a string has balanced parentheses if every left parenthesis is "matched" by a right parenthesis (of course this is far from being a formal definition). If there is no left parenthesis, then everything is OK.

Once you accept that, there is absolutely nothing wrong about the empty string – it is a string like any other. In particular, it is a string over your alphabet with balanced parentheses.

One way to formally define your language is using a context-free grammar. While there are many possible grammars, here is one that tried to capture the "matching" aspect when scanning the string from left to right:

$$ \begin{align*} &S \to \epsilon \\ &S \to xS \\ &S \to yS \\ &S \to (S)S \end{align*} $$

| cite | improve this answer | |
  • $\begingroup$ Thank you. I wasn't given a formal definition unfortunately, but in (roughly) the wording I stated in my OP. The real question is to design the PDA from the CFG. But - that I will do on my own, just couldn't figure out the "corner case" scenario I was pondering. Thanks! $\endgroup$ – NateH06 Jan 25 '17 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.