Theory of Computation: Question Set – 29

Theory of Computation: Question Set – 29

What is the difference between a regular expression and a regular language?

A regular expression is a pattern that describes a set of strings, while a regular language is the set of all strings that can be matched by a regular expression. Regular expressions are used in programming languages, text editors, and other applications to search for and manipulate strings.

What is the difference between a deterministic and a non-deterministic Turing machine?

A deterministic Turing machine is a theoretical model of a computer that can only perform one computation on a given input, while a non-deterministic Turing machine is a theoretical model of a computer that can perform multiple computations on a given input at the same time. Non-deterministic Turing machines are more powerful than deterministic Turing machines, as they can solve certain problems more quickly.

What is the difference between a context-free grammar and a regular grammar?

A context-free grammar is a formal grammar that can generate context-free languages, while a regular grammar is a formal grammar that can generate regular languages. Context-free grammars are more powerful than regular grammars, as they can generate more complex patterns in strings.

What is the difference between a language and a grammar?

A language is a set of strings that can be generated by a grammar, while a grammar is a set of production rules that describe how strings can be generated from a starting symbol. Languages are the objects of study in the theory of computation, while grammars are the tools used to generate and analyze languages.

What is the difference between a context-sensitive language and a recursively enumerable language?

A context-sensitive language is a formal language that can be generated by a context-sensitive grammar, while a recursively enumerable language is a formal language that can be recognized by a Turing machine. Recursively enumerable languages are more powerful than context-sensitive languages, as they can recognize more complex patterns in strings.

What is the Chomsky hierarchy?

The Chomsky hierarchy is a classification of formal languages based on the type of grammar needed to generate them. The hierarchy consists of four levels: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. Each level is a proper subset of the previous one, with the exception of the first two levels, which are equivalent.

What is the difference between a one-way and a two-way finite automaton?

A one-way finite automaton is a theoretical model of a computer that reads input from left to right and can only move the head of its tape to the right. A two-way finite automaton is a theoretical model of a computer that can move the head of its tape to the left or right. Two-way finite automata are more powerful than one-way finite automata, as they can recognize certain languages that one-way finite automata cannot.

What is the difference between a decision problem and a function problem?

A decision problem is a problem that can be answered with a simple “yes” or “no” answer, while a function problem is a problem that requires computing a specific output based on input. Decision problems are the focus of complexity theory, while function problems are the focus of computability theory.