Linked Questions
158 questions linked to/from How to prove that a language is not regular?
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 -
...
1
vote
1answer
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 ...
0
votes
0answers
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.
-2
votes
1answer
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 ...
-2
votes
1answer
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.
-1
votes
1answer
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, ...
0
votes
1answer
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?:)
-1
votes
1answer
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\}$
0
votes
1answer
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^*, \...
1
vote
0answers
65 views
Proving a language is regular or non-regular [duplicate]
I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints?
State whether the following languages are regular or not ...
1
vote
1answer
39 views
Proving that language is regular or not [duplicate]
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 ...