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.

Write a general example of interrupts in C language with comments. Thank you

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

1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs,...

1. regular expressions as a mechanism to specify tokens, 2. defining context-free grammars for language constructs, and 3. derivation of language terms and expressions based on a context-free grammar. 1 Regex 1. Define the regex for the following description of tokens: (a) Any string that starts with character t (b) Any string of at least length 3 that starts with t and ends with u (c) Any string that specifies the range of numbers between 11 and 23. (d) Any...

write a general example of polling in C language with comments

Question