Computer Theory

[ushak]

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

[ushak]

A question:

Can a language L, that is not recursive be infinite??

[charlieboy]

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.

[ushak]

Thank you charlieboy!

One more clarification.
Could there be a language for a recursive set which is not a recursive language?

[wood]

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.

[The_Wonderful_Vipul]

Originally posted by ushak

A question:

Can a language L, that is not recursive be infinite??

What do you mean if a language is infinite ?? ... what does this have to do with a recursive language .... if you mean that it can generate infinite strings, then I don't think that "recursive" and "infinite" are related.

Could you please elucidate ?

Vipul.

[nonevent99]

A language is a set of strings. An infinite language is an infinite set of strings.

Originally posted by The_Wonderful_Vipul

Originally posted by ushak

A question:

Can a language L, that is not recursive be infinite??

What do you mean if a language is infinite ?? ... what does this have to do with a recursive language .... if you mean that it can generate infinite strings, then I don't think that "recursive" and "infinite" are related.

Could you please elucidate ?

Vipul.

[Laks]

Guys help me out here...

A non recursive language can never be contained in a recursive set.
am I right????


Laks

[nonevent99]

Originally posted by Laks

Guys help me out here...

A non recursive language can never be contained in a recursive set.
am I right????


Laks

By "contained" do you mean "is a subset of"? What do you mean by "contained"?

[Laks]

"Contained" as in subset YES

Laks