Awesome q2a theme
+1 vote
34 views

What are these languages among them: Regular, DCFL, CFL, CSL, REC, RE ?

$L1=(w_{1}w_{2}: w_{1}\neq w_{2}: |w_{1}|=|w_{2}| )$

$L2=(a^nb^m: m=n^2,n\geqslant 1 )$

$\\L3=(w^n : w\epsilon (a,b)^+,n\geqslant 2)\\ L4=(www^R: w\epsilon (a,b)^+)$

$L5=(wuw^R: w,u \ \epsilon (a,b)^+, |w|\geqslant |u|)$

$L6=(a^nb^ma^{nm}: n\geqslant 1,m\geqslant 1)$

in Theory of Computation by (400 points) | 34 views
0
1 CSL

2 CSL

3 regular
0
5th one is ncfl... Remaing are csl…

Third one is not regular... W$^n$ =w.w...w (n times)
0
does cfl means dcfl in your comment?
0
It's a typo... Those are csl
0
From remaining CSL’s, how do we verify which are REC, RE?
0
It some what tough :(

We can distinguish RECURSIVE or RECURSIVE ENUMERABLE, by using membership property.

But distinguish RECURSIVE or csl is depends upon how much space it's using for calculation.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users May 2020
  1. Kushagra गुप्ता

    97 Points

  2. praveen modala

    15 Points

  3. ramcharantej_24

    15 Points

  4. abhishek tiwary

    12 Points

  5. srestha

    12 Points

  6. Dtiwari

    9 Points

  7. Shivateja MST

    8 Points

  8. ankitgupta.1729

    8 Points

  9. Rashimdixit

    7 Points

  10. Bhavya1902

    7 Points

7,376 questions
1,741 answers
10,682 comments
90,352 users