Articles of regular language

Proving that the language $\mathscr L$ is non regular using the pumping lemma

I need to prove that the language $\mathscr L=\{\text{all the binary words such that the number of ones divide the number of zeros}\}$ is non regular using the pumping lemma For example: $010010\in \mathscr L$ because that there are fore zeros and two ones and $4\big|_2$ but $11000100 \notin \mathscr L$ because that there are […]

Prove the intersection of regular languages is regular.

A, B are regular languages. Complement of a regular language is regular Union is regular Prove the intersection is regular. Using these definitions the proof in my book is: $\overline A$ is regular by 1 $\overline B$ is regular by 1 $\overline A \cup \overline B$ is regular by 2 $\overline{A\cup B}$ is regular by […]

Are regular languages necessarily deterministic context-free languages?

The original problem Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers. a) Is M-N necessarily context-free? b) Is N-M necessarily context-free? My attempt Since DCFLs are closed under complementation, if N is DCFL, then both a and b are true, but […]

Prove the following language is not regular

The set of strings of 0’s and 1’s, beginning with a 1, such that when interpreted as an integer, that integer is prime. I’m assuming the best way to move forward is to use the pumping lemma. I’m having difficulty developing a contradiction in this case because typically the membership criteria of the language involves […]

Is $L_1$ context free language?

Let $L = L_1 \cap L_2 $, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L is Not recursive Regular Context free but not regular Recursively enumerable but not context free. […]

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don’t understand why though. A programming language has open curly braces and corresponding closing ones. Wouldn’t one need a stack to track the braces? Hence, […]

Formal Languages – Regular Expression

I’ve been battling the following two questions for more than a day today. Write a regular expression (comprised of {a, b}) that contain at least two b and do not contain abb. Write a regular expression (comprised of {a, b}) that contain abba and do not contain baa. For the first part I wrote a […]

Application of Pumping lemma for regular languages

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular. According to the Pumping lemma for each regular language a word $w = xyz$ exists, that $$\forall n,k \in \mathbb{N} \text{ with } 0 < |y| \leq |xy| \leq n$$ applies: $$xy^kz \in […]

Formally prove that every finite language is regular

I know how to prove this informally, but don’t know what the formal proof should look like.

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I’ve been thinking how to do that for a few hours and still don’t know. I would be very grateful for help.