Tagged Questions

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 ...
61 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). ...
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 ...
210 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 ...
197 views

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 = ... 1answer 45 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 ... 1answer 26 views Give a regular expression for$A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$and$y$contains at least$k1$'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$... 1answer 50 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^+ = ... 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 ... 1answer 83 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 ... 1answer 97 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 ... 1answer 201 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) &= ... 1answer 209 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 ... 2answers 126 views Is this proof using the pumping lemma correct? I have this proof and it goes like this: We have a languageL = \{\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$... 1answer 124 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 ... 2answers 257 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 ... 1answer 243 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 ... 2answers 421 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$. 1answer 918 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, ...
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 ...
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 ...