-2
$\begingroup$

Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ?

An argument w is a member of L under the following rules...

Example1:

  1. If more than half of w's digits are 1's --> it is a member of L iff it is a member of language A (fill in your favorite decidable A to complete example).

  2. If more than half of w's digits are 0's --> it is a member of L iff it is a member of language B (fill in your favorite decidable B to complete example).

  3. If exactly half of w's digits are 1's and half are 0's then w is not a member of L.

Example 2:

  1. If w is longer than 10 bits it has to be a member of decidable language A to be a member of L

  2. If w is 10 bits or less it has to be a member of decidable language B to be a member of L.

The general question: are the above type of languages (discrete) well-defined?

The same way a function can be discrete or continuous I am nicknaming these types of definitions 'discrete' definitions for languages because based on what type of input you are, your rule (reason) for membership/non-membership can be different from other arguments'. I would assume this is ok? There does exist an argument that all discrete functions are not computable (or that all computable functions are continuous), but I don't think this argument holds if all the inputs are of finite precision (as is the case with finite binary strings)

$\endgroup$
  • 1
    $\begingroup$ I think i understand now. This is legal, as you can define $L$ however you want as long as the definition doesnt have contradictions (aka a word that is not in L but also is in L), and if $L\subset\Sigma^*$ $\endgroup$ – nir shahar Jun 8 at 18:26
  • 1
    $\begingroup$ It isnt any different from any other way to define $L$, and it has nothing to do with continuous or discrete functions $\endgroup$ – nir shahar Jun 8 at 18:27
  • $\begingroup$ @nirshahar what happens if under certain assumptions there are contradictions (a word that is not in L but also is in L)? Would this count as a proof that those assumptions are false about the language? Or, if you could find such assumptions, the whole definition would just be considered not well-founded? $\endgroup$ – DeeDee Jun 8 at 18:35
  • $\begingroup$ @nirshahar such as let's say the definition of L references a set of languages (like the L's above), and under the assumption that L is in the set referenced we get the contradiction you speak of. Would this count as a proof that L cannot be in the set? A proof by diagnolization of some sorts? Can you use the definition of L itself to ensure it is not in a certain set in this way? $\endgroup$ – DeeDee Jun 8 at 18:38
  • $\begingroup$ If you have a contradiction like that, it would mean that $L$ cannot be a valid set (as every element is either in the set or not, but not both obviously). You cannot use it to prove anything - as it is just an incorrect way to define something. And continuous functions can also be defined with multiple rules! For example, take the function $f(x)$ such that $f(x)=sin(x)$ for $x\ge 0$ but $f(x)=x$ for $x<0$. This function is continuous. $\endgroup$ – nir shahar Jun 8 at 19:29
3
$\begingroup$

A language $L \subseteq \{0,1\}^*$ is well-defined if, for each possible word $w \in \{0,1\}^*$, it is clearly specified whether $w$ is in $L$ or not.

This means that your rules must cover every case (for every word $w \in \{0,1\}^*$, at least one of your rules specifies whether $w$ is in $L$ or not), and that there are no contradictions (there does not exist any word $w \in \{0,1\}^*$ where one rule says that $w$ is in $L$ and another rule says $w$ is not in $L$).

Yes, you can use case analysis to define a language, or to define anything else (a set, a function, etc.), so long as the cases cover every case and do not contradict each other. This is not a matter of computer science; it is a matter of mathematics.

For both of your examples, yes, if the languages $A,B$ have been defined, then your definition of $L$ is well-defined.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

There does exist an argument that all discrete functions are not computable (or that all computable functions are continuous), but I don't think this argument holds if all the inputs are of finite precision (as is the case with finite binary strings)

There is indeed a notion of Continuous functions which correspond 1:1 with Computable functions. They are Scott Continuous functions on certain Domains. Those are not related to your definition of 'discrete' functions (at least not that I can tell).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ my understanding of this argument is if you define a function whose behavior at some real number changes it is not computable because we can't in general tell when our argument is equal to that real number because we cant in general tell if two real numbers are equal. This has to do with the possible infinity of the argument. This argument doesn't apply here because all inputs from the universe (0,1)* are finite. I talk about the analogy between continuous and discrete just based on these words as descriptors for the language description. multiple 'discrete' rules. or one 'continuous' one. $\endgroup$ – DeeDee Jun 9 at 18:58
  • $\begingroup$ i thought it was relevant to mention here as a potential barrier to defining multiple discrete rules for language membership as we could run into the same problem of knowing exactly when when condition vs the other is met... but we do not run into that problem because of ^ $\endgroup$ – DeeDee Jun 9 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.