Regular Closure

Let L 1 , L 2 , L 3 , L_1, L_2, L_3, \ldots be a sequence of regular languages . Which of the following statements must be true?

[ 1 ] [1] The language i = 1 2017 L i \displaystyle\bigcap_{i=1}^{2017} L_i is always regular.

[ 2 ] [2] The language i = 1 L i \displaystyle\bigcap_{i=1}^\infty L_i is always regular.

[ 3 ] [3] The language i = 1 L i \displaystyle\bigcup_{i=1}^\infty L_i is always regular.

Only [ 1 ] [1] [ 1 ] , [ 2 ] , [1], [2], and [ 3 ] [3] Only [ 3 ] [3] [ 1 ] [1] and [ 2 ] [2]

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mursalin Habib
Dec 1, 2017

Given any two regular languages L 1 L_1 and L 2 L_2 , their intersection, L 1 L 2 L_1\cap L_2 , is also regular. From a simple inductive argument, it follows that [ 1 ] [1] is true.

[ 3 ] [3] is not necessarily true. Remember that any language that contains exactly one string is regular. Set L i = { 0 i 1 i } L_i=\{0^i1^i\} (the set containing the string that has i i zeros followed by i i ones). i = 1 L i \displaystyle\bigcup_{i=1}^\infty L_i is therefore { 0 k 1 k k 1 } \{0^k1^k| k\geq 1\} . Call this language S S . S S is a non-regular language as shown in the wiki linked in the problem.

[ 2 ] [2] is also not true. Complement all of the L i L_i s in the previous paragraph. Since regular languages are closed under complementation, we are left with another sequence of regular languages the infinite intersection of which gives us the set S \overline{S} . Now, S \overline{S} can't be regular since its complement, S S is non-regular.

Nice problem! I am fond of Automata Theory too.

Agnishom Chattopadhyay - 3 years, 6 months ago

Log in to reply

Thanks!

The automata theory is really fun; especially if you're mathematically inclined.

Mursalin Habib - 3 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...