edited by
616 views
4 votes
4 votes

If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language.

  1. Regular   
  2. CFL but need not be regular      
  3. CSL but need not be a CFL      
  4. Recursive but need not be a CSL
edited by

1 Answer

Best answer
4 votes
4 votes
@shraddha Is it? In dictionary b comes after aab rt? But I assume this is defined somewhere.

If we can lexicographically order the strings we can get a TM for accepting the strings in the language and rejecting the strings not in the language. But still there is no guarantee that the amount of tape space required for this is linear in terms of the input which is the condition for a language to be CSL.
selected by
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,175 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
295 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
204 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4