Linked Questions

-1
votes
0answers
26 views

Finite State Machine that only accepts strings with number of 0's is less then number 1's [duplicate]

In case inf length of the strings (general case). In case we fix the maximum length. For example for strings with a size less than 12. Can you please suggest the diagram.
1
vote
2answers
307 views

Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$ To Prove: If given language is regular or not. I know that it is not a regular language but I am not able to come up with the string which I can ...
1
vote
1answer
404 views

Prove the language of numbers divisible by 3 is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
0
votes
1answer
68 views

Is this language L regular?

Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N} $)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar ...
14
votes
4answers
2k views

Is the language of words containing equal number of 001 and 100 regular?

I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a ...
0
votes
0answers
13 views
0
votes
0answers
16 views

Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
7
votes
3answers
2k views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
20
votes
4answers
65k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
0
votes
0answers
16 views

Regularity of language of words of prime length [duplicate]

Is the following language regular? $$ L_{\mathit{prime}} = \{ w \in \{0,1\}^* : |w| \text{ is prime} \}. $$ I have to either provide a DFA (if the language is regular), or prove that it is not ...
1
vote
1answer
29 views

Prove its not a regular language [duplicate]

I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language. Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language. I can prove it with pumping ...
2
votes
2answers
774 views

Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]

I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
0
votes
1answer
72 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?:)
0
votes
0answers
29 views

Proving a language is Not Regular without using Pumping Lemma? [duplicate]

I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction. $$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$ I've seen a ...
0
votes
1answer
63 views

Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...

15 30 50 per page
1
2 3 4 5
11