Decision Properties of Languages

Answers and Replies

  • #2
18,363
8,213
Thanks for the post! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?
 
  • #3
34,686
6,394
I'd trouble remembering decision properties of languages like Regular, CFL, RE, etc. So I made a table of it. Are all the entries of table correct or has some errors

[/PLAIN] [Broken]
Decision_Property.jpg
I don't think that we have much expertise in this somewhat esoteric area, which is probably why no one has responded.

You could help us out, though, but expanding the acronyms in your table.
RL = ?
DCFL = ?
CFL = ? (context-free language?)
CSL = ?
RE = ?

What does "Is L = ##\Phi ?## mean?
What do the other columns in the table mean?
What are L1 and L2?
 
Last edited by a moderator:
  • #4
142
1
I don't think that we have much expertise in this somewhat esoteric area, which is probably why no one has responded.

You could help us out, though, but expanding the acronyms in your table.
RL = ?
DCFL = ?
CFL = ? (context-free language?)
CSL = ?
RE = ?

What does "Is L = ##\Phi ?## mean?
What do the other columns in the table mean?
What are L1 and L2?
Here
RL=Regular Languages
DCFL=Deterministic Context Free Languages
CFL=Context Free Languages
CSL=Context Sensitive Languages
RE=Recursively Enumerable Languages

##1^{st}## Column "Membership" corresponding to a particular row says that, is it decidable that a given string belong to a given language.

##2^{nd}## Column "##L=\phi##" corresponding to a particular row says that, is it decidable that a given language empty or not "i.e Emptiness Test".

##3^{rd}## Column "##L=\sum##*" corresponding to a particular row says that, is it decidable that a given language infinite.

##4^{th}## Column "Is ##L_1=L_2##" corresponding to a particular row says that, is it decidable that a given languages ##L_1, L_2## are equal.

##5^{th}## Column "Is ##L_1 \subset L_2##" corresponding to a particular row says, is it decidable that a given language ##L_1## a subset of another given language ##L_2##.
 
  • #5
34,686
6,394
Thank you. Your question deals with things I don't know much about, but maybe the clarifications will help others to provide you with some insight.
 

Related Threads on Decision Properties of Languages

Replies
5
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
3K
Replies
8
Views
4K
Replies
5
Views
2K
Replies
67
Views
5K
Replies
80
Views
11K
Replies
9
Views
1K
Top