Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Decision Properties of Languages

  1. Jan 11, 2015 #1
    Last edited by a moderator: May 7, 2017
  2. jcsd
  3. Jan 16, 2015 #2
    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?
     
  4. Jan 16, 2015 #3

    Mark44

    Staff: Mentor

    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: May 7, 2017
  5. Jan 17, 2015 #4
    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##.
     
  6. Jan 17, 2015 #5

    Mark44

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Decision Properties of Languages
  1. Programming language (Replies: 10)

  2. Assembly language (Replies: 5)

  3. Computer language (Replies: 4)

  4. New Language? (Replies: 1)

  5. Beginner Language (Replies: 28)

Loading...