Regular and Context-free languages

[evinda]

Hello! (Wave)

Show,using the closure properties,that from the following languages over $\Sigma= \{ 0,1,2\}$,the first one is regular and the second one is context-free.

• $ \displaystyle{ L_1=\text{ the strings,that,when they contain at least one "000", } \\ \text{they contain also at least one "bbb" }}$
  
• $\displaystyle{ L_2=\text{ the sequences of balanced parenthesis, } \\ \text{ at which in one parenthesis,there can't be more than two pairs of parenthesis} \\ \text{(for example the language does not contain this string: "()(()()())()") }}$

That's what I have tried:

• $$M_1=(\Sigma^* \{ 000 \} \Sigma^*), M_2=(\Sigma^* \{ 111\} \Sigma^*) \\ L_1=(\Sigma^*-M_1) \cup M_2$$
  We conclude that $L_1$ is regular,from the closure under the complement and the union.
  $$$$
• We know that the language $P$ of balanced parenthesis is context-free and the language $B=\Sigma^* - (\Sigma^* ()()() \Sigma^*)$ is regular,as a complement of a regular language.
  
  Since $L_2=P \cap B$ is the intersection of a context-free language with a regular one, $L_2$ is context-free.

Could you tell me if it is right or if I have done something wrong? (Thinking)

 

[Evgeny.Makarov]

Hint: In typed text, every comma and period must be followed by a space.

Show,using the closure properties,that from the following languages over $\Sigma= \{ 0,1,2\}$,the first one is regular and the second one is context-free.

• $ \displaystyle{ L_1=\text{ the strings,that,when they contain at least one "000", } \\ \text{they contain also at least one "bbb" }}$

Since you are talking about "bbb", the language does not seem to be over $\Sigma= \{ 0,1,2\}$.

• $\displaystyle{ L_2=\text{ the sequences of balanced parenthesis, } \\ \text{ at which in one parenthesis,there can't be more than two pairs of parenthesis} \\ \text{(for example the language does not contain this string: "()(()()())()") }}$

This language is not over $\Sigma$ either. More importantly, I am not sure I understand the condition "inside every pair of parentheses, there can't be more than two pairs of parentheses". Are the following strings allowed: "( ((())) )", "( (()) () )"?

• $$M_1=(\Sigma^* \{ 000 \} \Sigma^*), M_2=(\Sigma^* \{ 111\} \Sigma^*) \\ L_1=(\Sigma^*-M_1) \cup M_2$$
  We conclude that $L_1$ is regular,from the closure under the complement and the union.

This is correct. Well done!

 

[evinda]

Hint: In typed text, every comma and period must be followed by a space.

I will take it into consideration..

Since you are talking about "bbb", the language does not seem to be over $\Sigma= \{ 0,1,2\}$.

Oh,sorry! I meant "111", instead of "bbb" .. (Tmi)

This language is not over $\Sigma$ either. More importantly, I am not sure I understand the condition "inside every pair of parentheses, there can't be more than two pairs of parentheses". Are the following strings allowed: "( ((())) )", "( (()) () )"?

I don't know.. (Sweating) It is only given that the substrings of the form $() \dots ()$ consist always of at most two pairs of parentheses.

This is correct. Well done!

(Happy)