CSO 322 Theory of Computation Assignment Questions
[ad_1]
CSO 322 Theory of Computation Assignment Questions
Instructions to Students
(i) Write in A4 sheets in neat and legible handwriting.
(ii) At the bottom of every page of the assignment, the student has to sign.
(iii) Scan as a single pdf file (maximum size < 10MB) and the filename should be your ROLL NO
(For example: 17123001.pdf).
(iv) The assignment has to be submitted only via the Google forms mentioned in the email.
Answer all Questions
- Define the following: (2 × 3 = 6)
(a) Turing Acceptable Language and Turing Decidable language. (b) Type 2 Grammar. (c) An n-tape Turing Machine and its configuration.
- State True or False. Justify your answer with a proof or a counter example appropriately. (3 + 3)
(a) If L1 ⊆ L2 and L2 is non-regular, then L1 is non-regular. (b) If L is accepted by a PDA in which no symbols are ever removed from the stack, then L is regular.
- Consider the grammar (3 + 3)
(a) on algebraic expressions with productions S → S + S | S − S | S ∗ S | S/S | (S) | a.
- Draw derivation tree corresponding to two different left derivations of the expression a + (a ∗ a)/a − a. ii. Write the rightmost derivation corresponding to each of the trees in (i). (b) with the following productions. Here, a, b are the terminals and all other symbols are variables with the
starting symbol S.
S → TD1D2, T → ABCT|ε, AB → BA, BA → AB, CA → AC, CB → BC, CD1 → D1C, CD2 → D2a, BD1 → D1b, A → a, D1 → ε, D2 → ε, i. Describe the language generated by this grammar. ii. Find a single production that could be substituted for BD1 → D1b so that resulting language would be
{xan|n ≥ 0,|x| = 2n, na(x) = nb(x) = n}
- Design a PDA that recognizes the language {aibjck|i, j, k ≥ 0 and i = j or i = k}. (4)
- Prove or Disprove: The language given by {0n1n0n1n|n ≥ 0} is a Context-free Language. (4)
6. Design a Turing Machine to show that the language {ss|s ∈ {a, b}∗} is recursively enumerable. What modifications are required on the machine to show that this language is also recursive. (4)
CSO 322 Theory of Computation Assignment Questions
Need Help with a similar Assignment?
The post CSO 322 Theory of Computation Assignment Questions appeared first on homeworkcrew.
[ad_2]
Source link
"96% of our customers have reported a 90% and above score. You might want to place an order with us."
