Scribd
Upload
8 views2 pages

Turing Machines and Finite Automata Basics

This document introduces the relationships between languages, machines, and grammars. It defines a language as a set of strings over a finite alphabet, where a string is the concatenation of symbols. Machines are described as having an input tape to read symbols from and finite state control, with variations possible through additional storage, heads, and head movement capabilities. Machines are primarily considered as language recognizers that accept or reject input strings. The basics section notes that languages are sets defined by membership criteria like listing elements or providing a rule/grammar, with the empty set represented by {} or Ø. Set notation and subset/proper subset relationships are also introduced.

Uploaded by

Lakshmi Pria
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
8 views2 pages

Turing Machines and Finite Automata Basics

This document introduces the relationships between languages, machines, and grammars. It defines a language as a set of strings over a finite alphabet, where a string is the concatenation of symbols. Machines are described as having an input tape to read symbols from and finite state control, with variations possible through additional storage, heads, and head movement capabilities. Machines are primarily considered as language recognizers that accept or reject input strings. The basics section notes that languages are sets defined by membership criteria like listing elements or providing a rule/grammar, with the empty set represented by {} or Ø. Set notation and subset/proper subset relationships are also introduced.

Uploaded by

Lakshmi Pria
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

Introduction:

We will study the relationships between languages, machines, and grammars. A language is a set of strings over a finite alphabet, where a string is the concatenation of zero or more symbols from the alphabet. Machines will always include a means of reading input from an input tape, one symbol at a time, and will contain some amount of finite state control. Additional storage and types of storage, additional heads and the ability to move the head(s) in different ways provide for variations in the machine models, and may allow machines to perform harder tasks or perform the same tasks faster. Machines with output capabilities may also be considered as generators of languages (they output exactly the strings of the language delimited in some fashion) or computers (given an input string, the machine may produce an output string and halt, or if the function is not defined for that input string, it may not halt). For the most part, we will consider machines as language recognizers, that is, given an input string, the machine will execute for some number of steps and halt in an accepting state or not (it may not halt, or it may halt in a non-accepting state). A general term for an automata. A machine could

be a Turing Machine, a pushdown automata, a finite state machine or any other restricted version of a Turing machine

Basics :Sets

Importance: languages are sets A set is a collection of "things," called the elements or members of the set. It is essential to have a criterion for determining, for any given thing, whether it is or is not a member of the given set. This criterion is called the membership criterion of the set. There are two common ways of indicating the members of a set: o List all the elements, e.g. {a, e, i, o, u} o Provide some sort of an algorithm or rule, such as a grammar Notation: o To indicate that x is a member of set S, we write x S o We denote the empty set (the set with no members) as {} or o If every element of set A is also an element of set B, we say that A is a subset of B, and write A B o If every element of set A is also an element of set B, but B also has some elements not contained in A, we say that A is a proper subset of B, an write A B

Need More

You might also like