Regular+CFG

Question

Comments

@cse23 By putting w=ϵ ,you are getting everything i.e.$\sum ^{*}$ and you can take any string which will belongs to $\sum ^{*}$

 

@Kunal Finite always means regualr.Enumerated .all the string belongs to $\left \{ www||w|\leq 100 \right \}$ and make FA.

---

ok but in first language By putting w=ϵ ,weare getting (t+0*) which is not ∑∗  ryt??

---

Yes I misinterpreted the qus.

you are correct .By putting w=ϵ ,we are getting (t+0*).

Here what is t. It seems the qus is bogus.

Answer 1

Let us see each of the following languages one by one :
 

Language (i) is not regular .Let us see how. Since we get regular expression for each of the cases when we substitute 0* and t for w and x one by one..In each case we get a regular expression..So the set generated will be a regular set..

For instance , we substitute w = x = 0* , so we get 0*..Similarly w = x = t , then we have a single string ttt..In general , the appropriate description would be to do these :

Now putting w = t and x = 0* and w^R = t only so we will get t(0*)t

Similarly put w = 0* and x = t so we get the regular expression 0ⁿ t 0ⁿ which as |w| = |w^R| so length needs to be same..So clearly 0t00 will not come in the above expression..So we can conclude that wxw^R  such that w = 0* and x = t is not regular..Hence we can conclude that the language is not regular..

w.x.w^R  = x = (t + 0*)..So all higher strings which were generated by w.x.w^R will get generated by x only by doing the above substitution..Hence langauge (i) is regular..

Language (ii) is regular as well since by substituting w = w^R  = ϵ , we get :

w.w^R.x  = x which is beyond doubt regular ..So all the strings under the Kleene's Closure are covered basically so necessarily it has to be regular..

Language (iii) is regular beyond doubt as it is a finite set and to model finite set we need finite memory hence can be modelled using finite automata..

Language (iv) is not even CFL since this cannot be implemented even by PDA i.e. by using 2 stacks..However it can be implemented using 2 stacks and hence can be done by LBA(Linearly Bounded Automata) and hence a CSL..

Hence none of the options are given correct here.So it should be corrected..

Comments

To keep track of the value of n what we do is we push a's first as soon as we get b in input so start popping the a's..

Now by the time c comes in input the stack will be empty and hence we do not know the specific value of n..So we cannot ensure that the number of c will be the same and more specifically 'n' as well.

---

Language 1st should nt be regular as string 0t00 string would nt belong to this as evident by 0^(*)t0^(*) includes it in

---

Yes language 1 is not regular.

Answer 2

http://gatecse.in/identify-the-class-of-a-given-language/

Comments

yes, but which type of language is i and ii??

---

Both languages are not DCFL. First language is not DCFL because x is a string, not a separate symbol.

---

are they CFL??

---

Yes both 1st and 2nd would be cfl