1

Thank you in advance if you can help me out with this.

So, i have a grammar that produces strings like [([([(00000)(01101)(011)])(000)])].

Non-empty ( ) can contain [ ] or any number of 0s and 1s.

Non-empty [ ] can only contain ( ).

And i need to know if the language of this grammar is regular or not.

So, in my understanding, i need to find a number, n, so that there is no way of dividing a string of the language in xyz that is in accordance with the three clauses of the lemma.

Following something i read in another stackexchange thread:

"That's not quite right. Think of the pumping lemma as a game:

Mr. Pumping Lemma gives you a constant n. You choose a word w in the language of length at least n. Mr. Pumping Lemma gives you x, y, and z with xyz=w, |xy|≤n, and y not empty. Now you pick r. Mr. Pumping Lemma asserts that xyrz is also in the language. If he's wrong, you win."

So:

1 - Let n be 2;

2 - i choose [()], but it can be any string, >=2, although this is the shortest one.

3 - There's no way of dividing [()] in xyz with xy<=2 and y>0 with xyrz being in the language:

if x = epsilon and y = [, then [[[()] is not in the language;

if x = epsilon and y= [(, then [([([()] is not in the language;

if x = [ and y = (, then [((()] is not in the language.

Therefore, the language is not regular.

Is this the correct application?

Thank you again!

remit
  • 11
  • No. Your first step was to choose $n$, but it should be chosen (being appropriately big for the given language) by Mr Pumping Lemma. I guess anyway that it's a regular language, it might be easier to directly build an automaton that accepts it. – Berci Apr 19 '18 at 10:44
  • First part I think I get it, its not up to me to set a pumping length. But, how can this be regular if there must be an equal number of open and closed parenthesis? – remit Apr 19 '18 at 13:22
  • Yes, that made me think too. I think I know: whatever $n$ is given, just start your word $w$ by $n$ opening brackets $[([(\dots$ then no part of it can be legally pumped.. – Berci Apr 19 '18 at 13:26
  • Ooh, that might be it!! Thanks you for your time – remit Apr 19 '18 at 13:32
  • The key point here is the requirement $|xy|\ge n$ where $y$ is pumped. I will post it as an answer.. – Berci Apr 19 '18 at 13:32
  • it's $y^r$ not $yr$. – Xoff Apr 19 '18 at 13:46

1 Answers1

1

Your approach is not entirely correct, as in the first step the $n$ should be chosen by Mr Pumping Lemma.

However, because the brackets must match, it won't be a regular language:
For any $n$ given in step 1, choose a word $w$ that starts with $n$ opening signs: $[([(\dots$. Then the $y$ to be pumped consists of only opening brackets, so the number of ending brackets will not match in a pumped version of $w$.

Berci
  • 90,745