Theory of Computation TOC : Regular, Non Regular, Context free Language Identification | 126
Playlist for all videos on this topic: • Theory of Computation or Automata Theory ...
shortcuts to check whether the given grammer is regular, context free, context sensitive or RE?determine the class of a language in TOC (CFL, recursive, r.e., det. context free, context sensitive)?
identify regular language
L1={ww|w is element of {a,b}* }
L2={wwR|w is element of {a,b}*,wR is reverse of w}
L3={0 raise to (2i)|i is an integer}
L4={o raise to (i raise to 2)|i is an iteger}
which lang is regualr?
language {a”b”|n 20}is context-free, but not regular
deterministic finite automaton (DFA),
nondeterministic finite automaton (NFA),
regular expression (regexp of formal languages) or
regular grammar
for some language L, then L is regular. There are more equivalent models, but the above are the most common.
There are also useful properties outside of the "computational" world. L is also regular if
it is finite,
you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as
intersection,
complement,
homomorphism,
reversal,
left- or right-quotient,
regular transduction
and more, or
using Myhill–Nerode theorem if the number of equivalence classes for L is finite.
In the given example, we have some (regular) langage L as basis and want to say something about a language L′ derived from it. Following the first approach -- construct a suitable model for L′ -- we can assume whichever equivalent model for L we so desire; it will remain abstract, of course, since L is unknown. In the second approach, we can use L directly and apply closure properties to it in order to arrive at a description for L′.
Proof by contradiction is often used to show that a language is not regular: let P a property true for all regular languages, if your specific language does not verify P, then it's not regular. The following properties can be used:
The pumping lemma,
Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.