Please write an example of a language that is Turing-decidable but not Context-Free. You can just...

Please write an example of a language that is Turing-decidable but not Context-Free. You can just state what the language is; no need to give a full TM algorithm for it.

1b) Please write an example of a language that is not Turing-decidable. You can just state what the language is; no need to give a full TM algorithm for it.

Expert Solution

Undecidable Problems
A problem is undecidable if there is no Turing machine which will always halt in finite amount of time to give answer as ‘yes’ or ‘no’. An undecidable problem has no algorithm to determine the answer for a given input.

Examples

Ambiguity of context-free languages: Given a context-free language, there is no Turing machine which will always halt in finite amount of time and give answer whether language is ambiguous or not.
Equivalence of two context-free languages: Given two context-free languages, there is no Turing machine which will always halt in finite amount of time and give answer whether two context free languages are equal or not.
Everything or completeness of CFG: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*)is undecidable.
Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or REC, determining whether this language is regular is undecidable.

Note: Two popular undecidable problems are halting problem of TM and PCP (Post Correspondence Problem). Semi-decidable Problems
A semi-decidable problem is subset of undecidable problems for which Turing machine will always halt in finite amount of time for answer as ‘yes’ and may or may not halt for answer as ‘no’.
Relationship between semi-decidable and decidable problem has been shown in

venereology answered 1 year ago

Can you give me a turing machine for the language c* n b2n a n+2 for...

Can you give me a turing machine for the language c* n b*2n a* n+2 for n>=0 . Please give the entire diagram with states, transition function, alphabet. Can use either one-tape or two-tape (both infinite). Describe the logic used to build the machine. Run the TM that accepts for any string of length > 1. Also run for string cbba.

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A,...

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved. R is a regular expression if RR is: a for some a∈alphabet Σ, the empty string ε, the empty set ∅, R1∪R2, sometimes written R1∣R2, where R1 and R2 are regular expressions, R1∘R2, sometimes written R1R2, where R1 and...

If you have a Turing machine with a tape that is not just linear at each...

If you have a Turing machine with a tape that is not just linear at each move, instead you have the ability to move up, down, left, or right. There is a single read/write head. The transition function looks like. The tape extends up and right infinitely. That is, you can never go left or down of where you start, but you can go infinitely up and to the right. Is this machine equivalent to the standard Turing machine model?...

5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language...

5 Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved.

Hi this is Assembly Language MASM x86 program. Please write it in the language and please...

Hi this is Assembly Language MASM x86 program. Please write it in the language and please explain it with comments thank you Please answer it I really need help this question was refunded before so please answer. Thank you so much also these are two separate programs thank you. 1) Write a procedure to read in decimal or hex number (byte-sized) Then write a procedure using shifts and ANDS to convert the string to a binary number (if is backward,...

Show that {xx^R | x,y ∈ {0,1}*} is a context-free language. Note that x^R is the...

Show that {xx^R | x,y ∈ {0,1}*} is a context-free language. Note that x^R is the reversal of x. Show all work. Question is for Discrete Math Structures

Hello, Can you please write a free plagiarism report about "Dryport a modal shift in practice",...

Hello, Can you please write a free plagiarism report about "Dryport a modal shift in practice", it has to be 500 words only. Thanks in advance

Please re write and re-organize the essay. Feel free to change the words. I just need...

Please re write and re-organize the essay. Feel free to change the words. I just need 750 words. Sexual predators and sex offenders are, as unfortunate as it is to say, nothing new. However, with the dawn of the internet and extensive social platforms in which everyone from the age 3-103 can interact on, new concerns about adolescents’ safety have emerged. The internet has brought with it a new arena in which sex offenders can coerce and manipulate adolescents. Parents...

on C++ language please and if you can also put note on it to better undertand...

on C++ language please and if you can also put note on it to better undertand it. Write a program that reads data from a data file, the value of which is provided at the end of the problem. Your program is to incorporate the following requirements: Data to the program is input from a file of an unspecified length; that is, the program does not know in advance how many numbers are in the file. Save the output of...

Can you please take this code and just rewrite it so it can be easily be...

Can you please take this code and just rewrite it so it can be easily be able to put into a complier. in java Implementation of above program in java: import java.util.HashMap; import java.util.Scanner; import java.util.Map.Entry; public class Shopping_cart { static Scanner s= new Scanner (System.in); // declare hashmap in which key is dates as per mentioned and Values class as value which consists all the record of cases static HashMap<String,Item> map= new HashMap<>(); public...

Question