Question

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)

Was it helpful?

Solution

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.

OTHER TIPS

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).

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top