0
votes
1answer
17 views

Prove that a language is not regular.

I want to ask how to prove the following language is not regular using closure properties. I tried to use pumping lemma but I find the proof itself shaky. I'd appreciate if you can help. The ...
0
votes
1answer
60 views

Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
1
vote
2answers
36 views

Prove by induction on a string

I want to practice proving the following: Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same. For ...
2
votes
1answer
129 views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
0
votes
1answer
194 views

Show that two disjoint languages are not separable

What is the general method to show that two disjoint languages are not separable? As an example, suppose we have: $A = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says ACCEPT$\}$ $B = ...
0
votes
1answer
44 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
1
vote
1answer
26 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
1
vote
1answer
47 views

Question about equlaity of two language, simple but tricky.

I found the following question tricky: If $A$ is a language, when will $A^*=A^+$? By definition, $$A^* = \bigcup^{\infty}_{i=0}A^i = A^0 \cup A^1 \cup A^2 \cup \cdots$$ $$A^+ = ...
1
vote
2answers
20 views

A question about operations on languages.

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so ...
0
votes
1answer
81 views

Prove that a Language is Non-Regular Using Closure Properties

Use the closure properties of regular languages and a language $B$ known to be non-regular to prove that a language $A$ is not regular. My understanding is that the closure properties only apply when ...
1
vote
1answer
96 views

Prove the following language is not regular

The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime. I'm assuming the best way to move forward is to use the pumping lemma. I'm ...
0
votes
1answer
194 views

Prove regular language closed under min and max

Given some regular language $L$, show that $L$ is closed under the following operations: $$\begin{align*} \min(L) &= \{w\mid w\in L,\text{ but no prefix of }w\text{ is in }L \}\\ \max(L) &= ...
0
votes
1answer
205 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
2
votes
2answers
122 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
1
vote
1answer
123 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
2answers
256 views

Pumping Lemma Excercise

I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
1answer
237 views

Proving a language is regular or irregular

I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...
1
vote
2answers
413 views

Showing that a language is regular - Pushdown Automaton

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
1
vote
1answer
909 views

Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let $Σ = \{0, 1, +, =\}$ and $\mathrm{ADD} = \{x = y + z \mid x, y, ...
2
votes
2answers
562 views

Prove that a language B is regular

here is the question I'm dealing with: Let B = {$1^{k}$y|y $\in$ {0,1}* and y contains at least k 1s, for k $\geq$ 1}. Show that B is a regular language. Can I use the pumping lemma to ...
2
votes
1answer
204 views

Using the pumping lemma to show that a language is not regular (Computer Science)

Show that $L=\{a^{n^2} | n \ge 0\}$ is not regular Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me. I tried to look if I get some contradiction by using the ...