δ 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
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
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
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