- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

The basic definitions of the fundamental concepts in the Theory of Computation (TOC) along with the relevant examples are explained below −

Symbols simply call it as a character.

It is an atomic unit, such as a digit, character, lowercase letter, etc. Sometimes it is also a word. The formal language does not deal with the “meaning” of the symbols.

For example,

- a,b,c,……………z
- 0,1,2,…………..9
- +,-,*,%,…………special characters.

The set of characters is called as the alphabet.

An alphabet is a finite, non-empty set of symbols. It is denoted by Σ or E.

For example,

- Σ ={0,1} set of binary alphabets.
- Σ ={a,b,c,……..,z} set of all lower case letters.
- Σ ={A,B,C,………Z} set of all upper case letters.
- Σ ={+,&,%,……….} set of all special characters.

A string is a finite set sequence of symbols choose from some alphabets

For example,

- 00011001 is a string from the binary alphabet Σ={0,1} and aabbcabcd is a string from the alphabet Σ={a,b,c,d}.
- If, w = 0110 y = 0aa x = aabcaa z = 111. Then,
- Special string − s (also denoted by X)
- Concatenation − wz = 0110111
- Length − |w| = 4 |s| = 0 |x| = 6
- Reversal − y
^{R}= aa0

Some special sets of strings are as follows −

- E* All strings of symbols from E
- E+ E* - {s}

For example,

- E = {0, 1}
- E* = {s, 0, 1, 00, 01, 10, 11, 000, 001,...}
- E+ = {0, 1, 00, 01, 10, 11, 000, 001,.}

It is the number of symbols in the string or word. It is denoted by |w|.

For example,

w=01011001 from binary alphabet Σ={0,1}

|w| = 8

X= abbaddabba from binary alphabet Σ={a,b}

|X| = 10

A language is a set of strings from some alphabet (finite or infinite). In other words, any subset L of E* is a language in TOC.

Some special languages are as follows −

- {} The empty set/language, containing no string.
- {s} A language containing one string, the empty string.

E = {0, 1}

L = {x | x is in E* and x contains an even number of 0’s}

E = {0, 1, 2,., 9, .}

L = {x | x is in E* and x forms a finite length real number}

= {0, 1.5, 9.326,.}

E = {a, b, c,., z, A, B,., Z}

L = {x | x is in E* and x is a Pascal reserved word}

= {BEGIN, END, IF,...}

E = {Pascal reserved words} U { (, ), ., :, ;,...} U {Legal Pascal identifiers}

L = {x | x is in E* and x is a syntactically correct Pascal program}

E = {English words}

L = {x | x is in E* and x is a syntactically correct English sentence}

- Related Questions & Answers
- What are the fundamental differences between Windows and Linux?
- What are the basic properties of products in TOC?
- What are the properties of Regular expressions in TOC?
- What are fundamental data types in C++ programming?
- What are the undecidable problems in TOC?
- What are basic Object oriented programming concepts?
- What are the Turing machine variations in TOC?
- What are the different operations performed on strings in TOC?
- What are the P class and NP class in TOC?
- Basic Concepts of Graphs
- What is the decision problem in TOC?
- What is the Halting Problem in TOC?
- C program demonstrating the concepts of strings using Pointers
- What is The Church-Turing Thesis in TOC?
- What is Decidability in TOC?

Advertisements