10-08-2003, 03:52 AM
|
#1 (permalink) |
|
Eager!
 Join Date: Oct 2003
Location: USA
Posts: 34
 |
Few basic points:
1. All finite languages are recursive 2. If L is recursive then L complement is also recursive 3. If L and L complement are r.e (recursively enumerable) then both are recursive 4. If S1 and S2 are finite and S1 is proper subset of S2 then S1 and S2 have different cardinality. However, if both S1 and S1 are infinite, both sets MIGHT have the same cardinality. Ex: S1 {set of even integers} S2 { set of all integers } f(2i) = i, hence the cardinality is equal for both sets in this case. Please feel free to add more when you guys come across any properties/relations/theories. Usha |
|
       
|
|
10-09-2003, 03:24 AM
|
#3 (permalink) |
|
Eager!
Join Date: Sep 2003
Posts: 34
|
Terminology is important here. The word "recursive" here is being used in the sense of "Turing decidable," not in the general sense of a langauge created by a grammar with self-referencing variables. So yes, a language can be non-recursive but still allow infinite strings.
|
|
|
|
|
10-11-2003, 06:56 PM
|
#5 (permalink) |
|
TestMagic Guru
 Join Date: Jul 2003
Location: Brazil
Posts: 1,360
|
Chomsky Classification + A Type 0 grammar is any phrase structure grammar without any restrictions - A Type 1 production has a left and right context of A. A is not consumed on the production. + A grammar is called type 1 or context-sensitive or context-dependent if all its productions are type 1 productions. - A Type 2 production is a production in the form A -> alpha. The L.H.S. has no left context or right context. + A grammar is called type 2 or context-free grammar if all its productions are type 2 productions. - A Type 3 production is a production in the form A -> a or A -> aB. + A grammar is called type 3 or regular expression if all its productions are type 3 productions. Recursive and Recursively Enumerable Sets (from Mishra's book, 2002 A procedure for solving a problem is a finite sequence of instructions which can be machanically carried out given any input. An algorithm is a procedure that terminates after a finite number of steps for any input. Definition: A set X is recursive if we have an algorithm to determine whether a given element belongs to X or not. Definition: A recursively enumerable set is a set X for which we have a procedure to determine whether a given element belongs to X or not. It is clear that a recursive set is recursively enumerable. Theorem: A context-sensitive language is recursive Theorem: There exists a recursive set which is not a context-sensitive language over {0,1}. Regular Sets/Grammars Theorem: Every regular expression R can be recognized by a transition system, i.e., for every string w in the set R, there exists a path from the initial state to a final state with path value w. Theorem: Any set L accepted by a finite automaton M is represented by a regular expression. Theorem: If L is regular then L^T is also regular. Theorem: If L is a regular set over E, then E* - L is also regular over E. |
|
|
|
|
10-12-2003, 01:56 AM
|
#6 (permalink) | |
|
Here I am !!
.gif)
Join Date: Feb 2003
Location: New York
Posts: 165
 |
Quote:
Could you please elucidate ? Vipul. |
|
|
|
|
|
10-12-2003, 06:01 PM
|
#7 (permalink) | ||
|
TestMagic Guru-in-Training
Join Date: Oct 2003
Location: USA
Posts: 508
|
A language is a set of strings. An infinite language is an infinite set of strings.
Quote:
|
||
|
|
|
|
10-15-2003, 09:56 AM
|
#9 (permalink) | |
|
TestMagic Guru-in-Training
Join Date: Oct 2003
Location: USA
Posts: 508
|
Quote:
|
|
|
|
|
Contact TestMagic TestMagic Forums Archive
Link to TestMagic
TestMagic Locations
Legal
Privacy
Partner Sites:
GMAT Sentence Correction
SAT 2400
Content Relevant URLs by vBSEO 3.0.0
Copyright © 1998-2008 TestMagic
Ad Management by RedTyger
Linear Mode
