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) 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 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 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 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 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 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…

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 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 (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…