recategorized by
1,597 views
0 votes
0 votes

Consider the following languages:

$L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$

$L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$

$L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$

Which of the languages is(are) regular?

Choose the correct answer from the options given below:

  1. $L_1$ and $L_2$ only
  2. $L_1$ and $L_3$ only
  3. $L_1$ only
  4. $L_2$ only
recategorized by

2 Answers

0 votes
0 votes
L1 =a^Z` ^Z where  Z` is an integer not regular

 in L2 first one is Z  a variable second is  Z` >=0   which is non negative integer (lets us call k)

 so L2= a^kz which is regular for any k=0,1,2 … as its DFA can be created

 L3= {ωω ∣ ωϵ{a,b}*}  not regular ( infinite comparison not possible in FA or even by PDA)

Hence D is right ans
0 votes
0 votes
L3 can be proven to be not regular by pumping lemma. Take $ a^{k}b^{k}a^{k}b^{k} $ where k is the pumping length.

L2 is regular because $a^{z z’} \forall ~ zz’ > 0 $ can be rewritten as $ a^{kz’} ~ \forall ~~ k > 0~ for ~a~ given ~z’ $ which is obviously regular. The DFA will have a z’ states and the last state will loop to the first.

L1 can be proven to be not regular by pumping lemma too. Let the pumping distance be $k$. Take the first values of $ a^{z’^{~m}} $ where $ z’ ^ {~m} > k $ . Now $ a^{z’^{~m+1}} = a^ { z’ ^ {~m} \times z’ }  >= 2* a^ { z’ ^ {~m} } \forall  z’ >= 2$. (Note that when z’=1, the language is regular and the language contains only one string). Now between $ z’^{~m} $ and $2*z’^{~m}$, there lies at least one values of $ k + n*p $ where $ 0<p<=k $ and $ n $ is the number of times the string of length $p$ is pumped. Note that we have taken $ z’ ^ {~m} > k $ . By division algorithm, $z’^{m} = q’ p + r , 0<=r<p$. Now $ z’^{~m}<(q’+1)*p<2*z’^{~m} $. This is not a part of $ a^{z’^{~z}} $. Hence it contradicts pumping lemma.
edited by
Answer:

Related questions