Prove that the languages are not regular

Assignment Help Theory of Computation

Reference no: EM13701619

Question: Prove that the subsequent languages are not regular using the pumping lemma. Use 'N' as the pumping lemma constant, to differentiate from the lowercase n used in parts a and b.

Part 1: {0n1m | n<=m}.

Part 2: {0n | n is a power of 2}.

Part 3: The set of strings of 0's and 1's that are of the form wwR, that is, some string repeated followed by its reverse.

I'm not sure how to solve the question. Can anyone help me?

Reference no: EM13701619

Questions Cloud

Magnitudes of their velocities : Two planes A and B are flying at the same altitude. if the magnitudes of their velocities are va = 500 km/h and vb=450km/h such that the angle between their straight line courses is theta=75 degrees , determine the magnitude in km/h of the velocity o..

Calculate the heat transfer rate for the intercoole : In a cold air-standard Brayton cycle, air enters a compressor operating at steady state at 15 lb/in2, 80 degress F, with a volumetric flow rate of 6000 ft3/min. The compression occurs in two stages and the pressure ratio across each stage is the same..

Case study : What do you think? Does this case present an ethical issue? If so, to which party (or parties)? If you could act as the ultimate authority on this situation, what would you do?

Design a class box that defines a box on a floor : You will Design a class box that defines a box on a floor. A box has a number and an (a,b) location where a and b are numbers between -5, and 5. The key member function is plot, which plots the box.

Prove that the languages are not regular : Prove that the subsequent languages are not regular using the pumping lemma. Use 'N' as the pumping lemma constant, to differentiate from the lowercase n used in parts a and b.

Convert the regular expressions to nfa : Convert the regular expressions to ? NFAs (Non-Deterministic Finite Automata). Use the modular building approach.

Perform a direct construction : Give a regular expression for each of the subsequent languages by performing a direct construction.

Provide a regular expression for the language : I am having trouble answering the subsequent question - Provide a regular expression for the language of binary strings containing at least two zeros somewhere.

Give english descriptions of the languages : Give English descriptions of the languages represented by the subsequent regular expressions. Example: "languages of binary strings containing 0 in even positions. . ."

User Account

All Pages