## CFG Properties and Applications

CFG Properties and Applications CFG- Context-free grammar is closure under: Union Concatenation Kleene Star Operation Union: Let suppose L1 and L2 are languages, they must have the finite set of…

## Chomsky Normal Form (CNF)

Chomsky Normal Form (CNF) It cannot contain the null, that CFG in which non-terminals belongs to two non-terminal. Or non-terminal belongs to only one terminal and non-terminal does not null,…

## Automata theory

Automata theory Automata theory is the branch of computer science that deals with the self-making languages and follows the predetermined sequence of operations. Something that performs its work without any…

## Finite automata

Finite automata Finite automata can be described into two types. 1: Deterministic Finite Automata (DFA). 2: Non Deterministic Finite Automata (NDFA). Deterministic Finite Automata: DFA can be described as The…

## Non-deterministic finite automata

Non-deterministic finite automata  Non-deterministic finite automata have the same DFA characteristic but a slight change. The total number of the alphabet should be finite. A total number of strings should be…

## Regular expression

Regular expression A regular expression can be defined as the following properties. Kleene Star Closure: Kleene star closure can be shown as ∑    =   Set of Alphabet ∑* =   Set…

## Moore machine and Mealy machine

Moore machine A Moore machine that consists of the following The finite number of states such as q0, q1, q2…qn where q0 is the initial state. Finite input alphabet such…

## Regular language

Definition of Regular Language A Regular language whose regular expressions can be drawn is known as regular language. Property of Regular Language: Closure Property: If L and M are two…

## FA to Regular Expression construction

FA to Regular Expressions construction This topic designed for finite automata FA to regular expression (RE) construction. Case 1: Finite Automata for RE = 0 For a regular expression (RE)…

## Pumping Lemma

Pumping Lemma (PL) Without any proof the string or language is accepted as true, this process is known as Pumping lemma. Pumping Theorem Let ‘L’ be a regular language. There…