163 questions linked to/from How to prove that a language is not regular?
146 views

How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\}$ is irregular? [duplicate]

We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\}$ is irregular (by the Pumping Lemma), we have to use it to prove two things: $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\}$ is irregular. $L_1$ is ...
140 views

How to prove that these two languages are regular, or not regular? [duplicate]

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
150 views

Proving that $\{0^nw1^n\mid n\geq 0, w\in\{0,1\}\}$ is irregular [duplicate]

How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.
135 views

Pumping lemma not regular [duplicate]

How would about proving this is not regular with the pumping lemma. Please include all steps and explain all steps. I am really new with this. $1^{2x}0^y$ and $y>= x$ Does it matter which side ...
81 views

Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
130 views

Pumping Lemma for regular language [duplicate]

I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as - ...
94 views

Prove language is not regular? [duplicate]

I know how to use the pumping lemma to do so, but I don't think that can be used for this language: $$L = \{x \in \{0,1\}^* : \text{no prefix of x has more 1's than 0's}\}.$$ What other ...
112 views

Is the language given by this CFG regular? [duplicate]

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
99 views

Formal Languages and Automata Theory [duplicate]

How can I show that $L = \{a^m b^n \mid (m > n \text{ or } m < n) \text{ and } m, n ≥ 1\}$ is not a regular language.
99 views

The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular [duplicate]

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)
65 views

How to prove a language isn't necessarily regular? [duplicate]

Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular. So far I can't come up with much for how to ...
79 views

is it possible to do a DFA for these languages? [duplicate]

I have just started learning Automata Theory, so far I only know about regular languages, FSM (NFAs and DFAs) and regular grammars, but I come across a question like this: "Given the next languages, ...
58 views

Pumping lemma of regular language [duplicate]

I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, \...
Given L is regular, Prove/Disprove that the following language is regular or not. $EXP = \{w| w^{|w|} ∈L\}$
How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not: $\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$ I started with the ...