What is a string in the context of formal languages? A finite sequence of symbols from an alphabet An infinite sequence of numbers A collection of alphabets A set of languages

A finite sequence of symbols from an alphabet

Which of the following statements best describes a formal language? A set of strings over a given alphabet A set of grammatical rules An infinite sequence of letters A mathematical model for computation

A set of strings over a given alphabet

Which of the following is NOT a characteristic of a regular language? Closed under union Closed under concatenation Closed under intersection Generated by a context-free grammar

Generated by a context-free grammar

What is the Kleene star operation on a set of strings? Generates all possible concatenations of strings Generates the power set of strings Creates a minimal spanning tree Finds the longest palindrome

Generates all possible concatenations of strings

Which of the following best defines a context-free grammar? A set of production rules that generate strings A set of alphabets with no production rules A sequence of strings with no grammar A regular expression equivalent

A set of production rules that generate strings

What is the Chomsky hierarchy of languages used for? Classifying languages based on their generative power Ordering languages by size Grouping languages by origin Describing the syntax of natural languages

Classifying languages based on their generative power

Which statement about Turing machines is true? They can recognize all recursively enumerable languages They can only recognize regular languages They are equivalent to finite automata They cannot compute non-deterministic algorithms

They can recognize all recursively enumerable languages

Which of the following is the correct formal definition of an alphabet? A finite set of symbols used to construct strings An infinite set of characters used for string manipulation A sequence of words following specific grammatical rules Any collection of letters from a language

A finite set of symbols used to construct strings

What defines a formal language? A set of strings over an alphabet An infinite set of symbols A sequence of numbers A set of equations

A set of strings over an alphabet

What does the power set of an alphabet represent? All possible subsets of the alphabet All possible strings of the alphabet An infinite set of strings A single string of the alphabet

All possible subsets of the alphabet

What is a key characteristic of context-free languages? They require a Turing machine for recognition They can be generated by context-free grammars They are recognized by pushdown automata They need linear-bounded automata for recognition

They can be generated by context-free grammars

Which class of languages is equivalent to the languages recognized by Turing machines? Regular languages Context-free languages Context-sensitive languages Recursively enumerable languages

Recursively enumerable languages

What is a distinguishing feature of recursively enumerable languages? They can be generated by regular expressions They can be decided by a finite automaton They can be recognized by a Turing machine They can be generated by context-free grammar

They can be recognized by a Turing machine

What type of formal language can be recognized by a Turing machine? Regular languages Context-free languages Context-sensitive languages Recursively enumerable languages

Recursively enumerable languages

Which formal language class includes all computable languages? Regular languages Context-free languages Context-sensitive languages Recursively enumerable languages

Recursively enumerable languages

What is a characteristic of context-sensitive languages? Generated by regular expressions Generated by unrestricted grammars Generated by context-sensitive grammars Recognized by finite automata

Generated by context-sensitive grammars

Which of the following is a property of regular languages? They can be expressed using regular expressions. They require a stack to be recognized. They are equivalent to Turing machines. They include all context-free languages.

They can be expressed using regular expressions.

Which class of formal languages is recognized by Turing machines? Regular languages Context-free languages Context-sensitive languages Recursively enumerable languages

Recursively enumerable languages

What distinguishes context-sensitive languages from context-free languages? Use of a stack Use of a finite automaton Grammar rules where the left-hand side is longer or equal to the right-hand side Inclusion in the Chomsky hierarchy

Grammar rules where the left-hand side is longer or equal to the right-hand side

Which of the following is true about recursively enumerable languages? They are a subset of recursive languages. They can be recognized but not necessarily decided by a Turing machine. They are equivalent to context-free languages. They are recognized by finite automata.

They can be recognized but not necessarily decided by a Turing machine.

Computer Science

Flashcard >
Science >
Computer Science

Flashcard sets

View All

Algorithms

Advanced Concepts in Alphabets Strings and Languages

user_nasirrxyq

MCQ 10 Cards

Algorithms

Understanding Alphabets Strings and Languages

user_nasirrxyq

MCQ 10 Cards

Algorithms

Types of Formal Languages Comprehensive Exploration

user_nasirrxyq

MCQ 10 Cards

Textbooks

View All

Expert Q&A

View All

Algorithms

Advanced Concepts in Alphabets Strings and Languages

user_nasirrxyq

MCQ 10 Cards

Algorithms

Understanding Alphabets Strings and Languages

user_nasirrxyq

MCQ 10 Cards

Algorithms

Types of Formal Languages Comprehensive Exploration

user_nasirrxyq

MCQ 10 Cards

Algorithms

Types of Formal Languages

user_nasirrxyq

MCQ 10 Cards

Algorithms

Types of Formal Languages Comprehensive Study

user_nasirrxyq

MCQ 10 Cards

Algorithms

Problem-Solving and Algorithmic Thinking

l226822rmkdiz

MCQ 10 Cards

Algorithms

Problem-Solving and Algorithmic Thinking

l226822rmkdiz

MCQ 10 Cards

Algorithms

Advanced Database Concepts Course Scope Learning Objectives

haroonnawacvyj

MCQ 10 Cards

Algorithms

Course Scope and Learning Objectives in Advanced Database Concepts

haroonnawacvyj

MCQ 10 Cards

Algorithms

Advanced Database Course Scope and Learning Objectives

haroonnawacvyj

MCQ 10 Cards

Algorithms

The Critical Role of Algorithms in Computer Science

l226822rmkdiz

MCQ 10 Cards

Algorithms

Importance of Algorithms in Computer Science

l226822rmkdiz

MCQ 10 Cards

Algorithms

The Importance of Algorithms in Computer Science

l226822rmkdiz

MCQ 10 Cards

Algorithms

Understanding Types of Parallelism

user_bukharintxhx

MCQ 10 Cards

Algorithms

Types of Parallelism in Computing

user_bukharintxhx

MCQ 10 Cards