Group A presention

Multiple Choice

What is the purpose of the Theory of Computation?

• To study algorithms

• To define programming languages

• To find deep understanding of computational processes

• To create new machines

Fill in the Blanks

What are the four types of grammars in the hierarchy of computational models?

Open Ended

Explain the Chomsky hierarchy.

Multiple Choice

What are the key characteristics of regular languages?

• Recognizable by a finite automaton

• Describable by a context-free grammar

• Closed under arbitrary nesting

• Generated by context-free grammars

Poll

What is the primary difference between a Mealy Machine and a Moore Machine?

• In a Mealy Machine, the outputs depend only on the current state.

• In a Moore Machine, the outputs depend only on the current state.

• In a Mealy Machine, the outputs depend on the current state and the input.

• There is no difference; both machines function identically.

Fill in the Blanks

What is the role of a stack in recognizing context-free languages (CFL) by Pushdown Automata (PDA)?

Multiple Choice

What do Turing Machines represent in computing?

• A type of computer

• A universal computational model

• A programming language

• A hardware component

Multiple Choice

Sarah is trying to determine whether a question is undecidable or not. Which of the following would help her determine the question is undecidable?

• Proving that the question has a unique solution
• Demonstrating that the question can be easily solved by a computer
• Showing that the question is irrelevant to the topic
• Showing that no algorithm can provide a yes or no answer for the question

Multiple Choice

Which of the following topics is NOT mentioned in the image?

• Compiler Design

• Cryptography

• AI & Machine Learning

• Data Structures

Multiple Choice

What are the three major branches of the Theory of Computation?

• Automata Theory, Computability Theory, Computational Complexity Theory

• Data Structures, Algorithms, Software Engineering

• Artificial Intelligence, Machine Learning, Data Science

• Computer Networks, Operating Systems, Database Systems

Multiple Choice

What is one of the models discussed in Automata Theory that is used in text processing and compiler design?

• Finite Automata

• Context Free Grammar

• Regular Expressions

• Turing Machines

Multiple Choice

What is the function of the head in a Turing machine?

• It stores the state transitions.

• It reads from and writes to the tape.

• It decides the next state of the machine.

• It powers the machine.

Multiple Choice

What is a Turing machine?

• A physical machine for data encryption

• A theoretical model of computation

• An early version of the modern computer

• A high-speed computer

Multiple Choice

How does a Turing machine differ from a finite automaton?

• A Turing machine has a limited number of states, while a finite automaton has an unlimited number of states.

• A Turing machine has an infinite tape, while a finite automaton has a finite number of states and transitions.

• A Turing machine can only process regular languages, while a finite automaton can process any language.

• A Turing machine has a fixed tape length, while a finite automaton has an infinite tape.

Multiple Choice

What is the definition of a language according to Chomsky?

• A set of letters called Alphabet

• A collection of words

• A mathematical formula

• A set of numbers

Multiple Choice

What does the symbol Σ represent in the context of alphabets?

• A mathematical constant

• A finite set of symbols

• A type of equation

• A variable

Multiple Choice

What is the definition of a symbol in mathematical terminology?

• A basic building block of ToC

• A type of alphabet

• A mathematical operation

• A numerical value

Multiple Choice

What is the definition of a string in mathematical terminology?

• A sequence of numbers

• A finite sequence/group of symbols

• A random collection of letters

• A type of mathematical equation

Multiple Choice

What does |w| represent in the context of strings?

• The length of the string

• The position of a character

• The type of the string

• The content of the string

Multiple Choice

What is the value of Σ^0 when Σ = {0,1}?

• {0}

• {1}

• {λ}

• {0,1}

Fill in the Blanks

What is the letter Z

Fill in the Blanks

Fill in the blank: The alphabet used in the examples is

= {a, b}.

Multiple Choice

What are the rules for accepting sentences in the given example?

• Sentences must start with 'b'

• Sentences must start with 'a'

• Sentences can start with any letter

• Sentences must be of even length

Multiple Choice

What does the Commutative Law state about the order of sets in union or intersection?

• The order of sets matters for union.

• The order of sets does not matter for union or intersection.

• The order of sets is irrelevant for intersection only.

• The order of sets is important for both operations.

Multiple Choice

Using DeMorgan's Law, find the equivalent boolean expression to: ~(~A & (B | ~C))

• A & ~(B & ~C)

• ~A | ~(B | ~C)

• A | (~B | C)

• A | (~B & C)

Multiple Choice

What is the function of 'reverse' as described in the text?

• It spells a word backward

• It changes the letters of a word

• It counts the number of letters

• It creates a new word

Poll

How confident do you feel about this topic now?

• Very confident
• Somewhat confident
• Not confident