158 questions linked to/from How to prove that a language is not regular?
121 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 ...
196 views

### How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages? [duplicate]

I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \{a,b,c\}^*$ is kinda ...
129 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 ...
76 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 ...
124 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 - ...
92 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 ...
117 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.
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 ...
87 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.
77 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, ...
75 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?:)
53 views

### Prove EXP to be regular or non-regular [duplicate]

Given L is regular, Prove/Disprove that the following language is regular or not. $EXP = \{w| w^{|w|} ∈L\}$
53 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^*, \...
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 ...