Prove L = {a^nb^2n } is not regular
Theorem :Let L be a regular language.Then there exists a constant ‘c’ such that for every string s in L: |s| ≥ cWe can break w into three strings, s = xyz,…
Prove L = {a^n b^n+1} is not regular
Theorem :Let L be a regular language. Then there exists a constant ‘c’ such that for every string s in L:|s| ≥ cWe can break w into three strings, s =…
Find the grammar of the language L (G) = {a^m b^n | m> 0 and n ≥ 0}
Since L(G) = {am bn | m> 0 and n ≥ 0}, the set of strings accepted by the language can be written as:L(G) = {a, aa, ab, aaa, aab…
Find the grammar for the L (G) = {a^m b^n | m ≥ 0 and n > 0}
Since L(G) = {am bn | m ≥ 0 and n > 0} the set of strings accepted by the language can be written as:L(G) = {b, ab,bb, aab, abb,…
Algorithm for conversion of Moore Machine to Mealy Machine
Algorithm Input: Moore MachineOutput: Mealy MachineStep 1: StartStep 2 :Take a blank Mealy Machine transition table format.Step 3 :Copy all the Moore Machine transition states into this table format.Step 4: Check the…
Difference between Mealy Machine and Moore Machine
Mealy MachineOutput depends both upon present state and present input.Mealy machines react faster to inputsOutput changes at the clock edgesGenerally, it has fewer states than Moore Machine. Moore MachineOutput depends…
Algorithm for DFA Minimization using Equivalence Theorem
If A and B are two states in a DFA, we can combine these two states into {A, B} if they are not distinguishable. Two states are distinguishable, if there…
Prove that L = {a^k | k is a prime number} is not regular
Proof by contradiction:Let us assume L is regular. Clearly L is infinite (there are infinitely many prime numbers). From the pumping lemma, there exists a number n such that any…
Prove that L={ all strings of 1’s whose length is prime} is not regular. i.e., L={1^2,1^3 ,1^5 ,1^7 ,1^11 ,—-}
Suppose the statement is true, and this langauge is regular. Then there exists a FSA(finite state automaton) that recognizes this language, which we call M. The pumping lemma says that…
Prove pumping lemma
For every regular language there is a finite state automaton (FSA) that accepts the language. The number of states in such an FSA are counted and that count is used…
- 1
- 2
- 3
- 4
- …
- 6
- Go to the next page