Recursive languages vs context-sensitive languages

Posted by teehoo on Stack Overflow See other posts from Stack Overflow or by teehoo
Published on 2010-06-16T21:14:21Z Indexed on 2010/06/16 21:32 UTC
Read the original article Hit count: 470

Filed under:

homework

|

formal-languages

|

chomsky

In Chomsky's hierarchy, the set of recursive languages is not defined. I know that recursive languages are a subset of recursively enumerable languages and that all recursive languages are decidable.

What I'm curious about is how recursive languages compare to context-sensitive languages. Can I assume that context-sensitive languages are a strict subset of recursive languages, and therefore all context-sensitive languages are decidable?

© Stack Overflow or respective owner

Related posts about homework

parsing a list and producing a structure of that

as seen on Stack Overflow - Search for 'Stack Overflow'
;; structure representing homework points ;; nr: number - the number of the homework ;; points: number - the number of points reached (define-struct homework (nr points)) ;; parse-homework: (list of number pairs) -> (list of homework) ;; The procedure takes a list of number pairs and produces… >>> More
Scheme homework help

as seen on Stack Overflow - Search for 'Stack Overflow'
Okay so I have started a new language in class. We are learning Scheme and i'm not sure on how to do it. When I say learning a new language, I mean thrown a homework and told to figure it out. A couple of them have got me stumped. My first problem is: Write a Scheme function that returns true (the… >>> More
Unix [Homework]: Get a list of /home/user/ directories in /etc/passwd

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm very new to Unix, and currently taking a class learning the basics of the system and its commands. I'm looking for a single command line to list off all of the user home directories in alphabetical order from the /etc/passwd directory. This applies only to the home directories, and not the contents… >>> More
sequential search homework question

as seen on Stack Overflow - Search for 'Stack Overflow'
Consider a disk file containing 100 records a. How many comparisons would be required on the average to find a record using sequential search, if the record is known to be in the file? I figured out that this is 100/2 = 50. b. If the record has a 68% probability of being in the file, how many comparisons… >>> More
[Homework] Online programming editor

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, For a school project i need to write or use a online programming editor. It is a part of a bigger project. I thought of a java application, php/html/javascript or flash. I have a couple of things i could do: Find a good working application and edit it so it works with the rest of the project Find… >>> More

Related posts about formal-languages

Formal Languages, Inductive Proofs & Regular Expressions

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
So I am slogging away at my UNISA stuff. I have just finished doing the initial once non stop read through the first 11 chapters of my COS 201 Textbook - “Introduction to Computer Theory 2nd Edition” by Daniel Cohen. It has been an interesting couple of days, with familiar concepts coming up as well… >>> More
Theory of formal languages - Automaton

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi everybody ! I'm wondering about formal languages. I have a kind of parser : It reads à xml-like serialized tree structure and turn it into a multidimmensionnal array. I figured out that i need at least three variables to achieve the job : $tree = array(); // a new array $pTree = array(&$tree);… >>> More
Shift-reduce: when to stop reducing?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to learn about shift-reduce parsing. Suppose we have the following grammar, using recursive rules that enforce order of operations, inspired by the ANSI C Yacc grammar: S: A; P : NUMBER | '(' S ')' ; M : P | M '*' P | M '/' P ; A : M | A '+' M … >>> More
Is the valid state domain of a program a regular language?

as seen on Stack Overflow - Search for 'Stack Overflow'
If you look at the call stack of a program and treat each return pointer as a token, what kind of automata is needed to build a recognizer for the valid states of the program? As a corollary, what kind of automata is needed to build a recognizer for a specific bug state? My thought is that if… >>> More
chomsky hierarchy and programming languages

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I'm trying to learn some aspects of the CH ( chomsky hierarchy ) which are related to PL ( programming languages ), and i still have to read the Dragon Book. I've read that most of the PL can be parsed as CFG ( context free grammar ). In term of computational power, it equals the one of a pushdown… >>> More