(1) Languages in the Chomsky hierarchy are listed in the left column of the following table....

Transcribed Image Text:

(1) Languages in the Chomsky hierarchy are listed in the left column of the following table. Please list the corresponding machine in the right column of the following table that accepts the language on its left. Language Recursively Enumerable Context Sensitive Context Free Regular Machine Name (2) Give four examples of undecidable problems regarding context-free languages (3) For A = (001, 0011, 11, 101) and B = {01, 111, 111, 010), find out a PC-solution. (4) Provide Boolean values (0 or 1) of x₁, x₂, x3 that make the following expression is satisfiable (i.e., the value of the expression is 1.) (x₁ V X₂ V X3) ^ (x₁ V X₂ V X3) ^ (x₁ V X₂ V X3) (1) Languages in the Chomsky hierarchy are listed in the left column of the following table. Please list the corresponding machine in the right column of the following table that accepts the language on its left. Language Recursively Enumerable Context Sensitive Context Free Regular Machine Name (2) Give four examples of undecidable problems regarding context-free languages (3) For A = (001, 0011, 11, 101) and B = {01, 111, 111, 010), find out a PC-solution. (4) Provide Boolean values (0 or 1) of x₁, x₂, x3 that make the following expression is satisfiable (i.e., the value of the expression is 1.) (x₁ V X₂ V X3) ^ (x₁ V X₂ V X3) ^ (x₁ V X₂ V X3)

Answer rating: 100% (QA)

1 Language Machine Name Recursively Enumerable Turing Machine Context Sensitive Linear Bounded Autom... View the full answer