What you’re looking for is Pumping lemma for regular languages. Here is an example with your exact problem: Examples: Let L = {ambm | m ≥ 1}. Then L is not regular. Proof: Let n be as in Pumping Lemma. Let w = anbn. Let w = xyz be as in Pumping Lemma. Thus, xy2z … Read more
Answer to your question: imagine a*b* to be regular, Is there a proof for it being regular or not? No need to imagine, expression a*b* is called regular expression (re), and regular expressions are possible only for regular languages. If a language is not regular then regular expression is also not possible for that and … Read more
δ is like a mathematical function called the transition function . Something like. z = f(x, y) A function in mathematical defines mapping of elements in one set to another set. In function set of input arguments are called Domain of a function and output is the rage. [ANSWER] In expression “δ:Q×Σ → Q”, … Read more
Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar. So for a palindrome for instance, is of the form, S->ABA A->something B->something You can clearly see that palindromes cannot be expressed … Read more
Regular Expression to DFA Although there is NO algorithmic shortcut to draw DFA from a Regular Expression(RE) but a shortcut technique is possible by analysis not by derivation, it can save your time to draw a minimized dfa. But off-course the technique you can learn only by practice. I take your example to show my … Read more
How to write regular expression for a DFA using Arden theorem Lets instead of language symbols 0,1 we take Σ = {a, b} and following is new DFA. Notice start state is Q0 You have not given but In my answer initial state is Q0, Where final state is also Q0. Language accepted by is … Read more
As you says in question: I know that to convert a DFA, M to the complement, M`, I just need to swap the initial accepting states and final accepting states. Its not complement, but you are doing something like reverse of a language and regular languages are closure under reversal. Reversal of DFA What is … Read more
Constructing an equivalent Regular Grammar from a Regular Expression First, I start with some simple rules to construct Regular Grammar(RG) from Regular Expression(RE). I am writing rules for Right Linear Grammar (leaving as an exercise to write similar rules for Left Linear Grammar) NOTE: Capital letters are used for variables, and small for terminals in … Read more