Linked Questions

0
votes
0answers
26 views

Using Nerode theorem to prove that the following languages are non-regular

I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked. The problem is to prove the ...
3
votes
1answer
90 views

Is the language of words with equal number of 010s and 101s as substrings regular?

Is the language of words containing same number of 101s and 010s regular? If yes, how can I design a DFA for it? In general, is the language of words containing equal number of strings which one is "...
0
votes
1answer
56 views

DFA for $L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$ Any idea? I have problem with this kind of task.
1
vote
1answer
76 views

Pumping Lemma vs Myhill-Nerode [duplicate]

I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much. Let us take the following as an example: $$ L = \{ a^n b^n \mid n \ge 0\} $$ ...
0
votes
0answers
74 views

Show that the language L = {www : w ∈ {0, 1} ∗} is not regular [duplicate]

Hey was wondering if I'm applying the pumping lemma correctly for this proof or if this proof could be improved? Suppose $L = \{www:w\in\{0,1\}^*\}$ is a regular language. Let $p$ be the number from ...
1
vote
1answer
47 views

Why is this not recognized by a DFA?

I am still confused over my professor's explanation on why this problem is not a DFA. The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA My professor explained it as ...
-2
votes
1answer
52 views

Provide “regular” grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$} [duplicate]

I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$ } Thanks.
2
votes
1answer
84 views

How to choose a word to apply the Pumping Lemma?

I have some questions about the PUMPING LEMMA. First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes. And sorry about my English :) ...
2
votes
0answers
53 views

If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]

How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
1
vote
1answer
60 views

How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

How to show that the following language is not regular with the pumping lemma? $$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$
-1
votes
1answer
55 views

Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
0
votes
0answers
17 views

Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
1
vote
1answer
35 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 ...
1
vote
1answer
189 views

Proving that no finite automaton can recognize a Dyck language

I was reading up on finite automata and I came across an interesting fact near the end of the Wikipedia page. The classic example of a simply described language that no DFA can recognize is ...
0
votes
0answers
52 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...

15 30 50 per page