Back to Other Questions [Of this Course]
👁️ 49 views
University of Barishal Logo

University of Barishal

Department of Computer Science and Engineering

1st Mid Exam

Course Title: Theory of Computation (CSE-3203)

Semester: 6th | Session: 17-18

Time: N/A | Marks: N/A

Exam Date: October 30, 2022

View 125 Topic-wise Questions for this Course
1.

A) Describe about Chomsky hierarchy (occasionally referred to as the Chomsky-Schützenberger hierarchy). This hierarchy of grammars was described by Noam Chomsky in 1956 It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages. Chomsky Hierarchy represents the class of languages that are accepted by the different machine. The category of language in Chomsky's Hierarchy is as given below: 1. Type 0 known as Unrestricted Grammar or Recursively enumerable grammar. 2. Type 1 known as Context Sensitive Grammar. 3. Type 2 known as Context Free Grammar. 4. Type 3 Regular Grammar Describe all type.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
0 Marks
B) Let, ∑ = {0, 1} Develop a DFA and make a transition table for the following language: L = {w | w is a bit string which contains the substring 11}

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
0 Marks
C) Let, ∑ = {0, 1} A DFA for the following language: L = {w | w is a binary string that has even number of 1s and even number of 0s} Let the string 110101. Calculate the extension of transition to paths.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
0 Marks
D) For the keyword recognizer occurrences of the words "include", Make a transition diagram.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
0 Marks
E) Make a NFA: Strings where the first symbol is present somewhere later on at least once.

Please SUBSCRIBE to view full question

Topics: N/A Solution is Coming!
0 Marks
View 125 Topic-wise Questions for this Course

Contributors of this Question:

Role Name Date
Uploaded By: Onebyzero Edu (Test User) July 30, 2024, 6:33 p.m.
Converted By (Img/PDF to Text): Baishakhi Bir Nov. 19, 2025, 1:01 p.m.
Reviewed By: Obaydul Hasan Nayeem Nov. 19, 2025, 5:20 p.m.
Back to Other Questions [Of this Course]