Miscellaneous Topics TOC

Terminology related to TOC

1. Alphabet (Σ)

• It is a finite, non-empty set of symbols.
• For example: Σ = {a, b}

2. String

• It is a finite sequence of symbols from an alphabet.
• For example: abba

3. Language (L)

• It is a set of strings over an alphabet.
• For example: L = {a, ab, abb}

4. Grammar

• These are rules that generate a language.
• There are several types of grammar, such as Regular, Context-Free, and Context-Sensitive.

5. Automata

• It is an abstract machines that recognize languages.
• For example, DFA, NFA, PDA, and Turing Machine, among others.

6. Regular Expression

• It is a pattern describing a regular language.
• For example, (a+b)*

7. Finite Automaton (FA)

• It is a machine with finite states.
• It recognizes regular languages.

8. Pushdown Automaton (PDA)

• It is an Automaton with a stack.
• It recognizes context-free languages.

9. Turing Machine

• This is the most powerful computational model.
• It defines computability.

10. Decidability

• It states whether a problem can be solved by an algorithm.

11. Complexity

• It measures the time and space required by algorithms.

12. Closure Properties

• It is the operations under which languages remain in the same class.
• For example, union, concatenation, star, etc.