0
$\begingroup$

Two sets of strings resulted from a set represented by binary and decimal code are in the same class of languages as regular languages,context-free languages,context-sentive languages ,computable languages and c.e.language?

For example,a set of number is represented by binary code,every number in the set form a 0-1 string,suppose the set of string is in RL,CFL,CSL,CL,c.e.L if the set of number is represented by decimal code,the set of strings is in the same class of the corresponding binary one?

since the transformation algorithm is in P,they seem to have to be in the same class.

second question:under what condition is the set of strings resulted from the sets of numbers in RL,CFL,CSL,CL,c.e.L?or the set of strings resulted from what sets of numbers is in RL,CFL,CSL,CL,c.e.L?

$\endgroup$
5
  • $\begingroup$ This is hard to parse. Do you mean you have a set of numbers and you consider X the binary string representing these numbers and Y the decimal string and you want to know if they are in the same language classes? $\endgroup$ May 7, 2014 at 10:49
  • 2
    $\begingroup$ Can it not be done by a transducer which preserved these classes? $\endgroup$ May 7, 2014 at 10:51
  • $\begingroup$ @BenjaminSteinberg, every number in a set of numbers corresponds to a string in a language by representing itself with binary code or decimal code.The two languages of the number set by different representation of binary base and decimal base is in the same class? $\endgroup$ May 7, 2014 at 13:04
  • $\begingroup$ @BenjaminSteinberg,I am not sure,so I post the questions to ask for proof or reference. $\endgroup$ May 7, 2014 at 13:06
  • $\begingroup$ To detail the answer of Benjamin Steinberg: you have a transducer (i.e. an finite-state machine) that can change between binary and decimal representation. All the classes of languages you mentioned are preserved by applying a transducer, so the answer to your question is yes. $\endgroup$
    – Denis
    May 13, 2014 at 13:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.