The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
54 views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
0
votes
1answer
197 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
39 views

showing language that is non-regular using pumping lemma

I am looking over pumping lemma and the author is using it to show that the language is non-regular. {a^n b^n a^n} = {aba aabbaa aaabbbaaa........} Is there ...
0
votes
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 ...
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$ ...
0
votes
2answers
122 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
1
vote
1answer
40 views

Regular languages and intersection

Let L be a language and R an infinite regular one. If L intersection R is a regular language, then L is a regular one too?
1
vote
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^+ = ...
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 ...
2
votes
1answer
42 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
1
vote
1answer
20 views

Is the language regular or contextfree?

Could you tell me if the language $$L=\{ w \in \{a,b,c\}^*: $$$$\text{there is at least one time the substring abc and none of the symbols a,b,c is repeated three times} \}$$ is regular or ...
1
vote
1answer
24 views

Use closure properties for the language $L=\{a^kb^l:|k-l| \leq 100 \}$

Given the language $$L=\{a^kb^l:|k-l| \leq 100 \}$$ I have to show that $L$ is regular or context free using closure properties. I have done the following: The language is regular. Let $k>l$, then ...
1
vote
1answer
22 views

How can I show that the language is regular using the closure properties?

How can I show that the language $L=\{ w \in \{a,b\}^*: \text{ the word w contains an even number of a and an odd number of b} \}$ is regular using the closure properties?
1
vote
1answer
32 views

Pumping Lemma Squares Proof Explanation

I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ...
0
votes
2answers
321 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
2
votes
1answer
33 views

Is the language L regular?

Could you tell me if the language $L=\{a^ib^j:i+j=k, k \geq 2 \}$ is regular? Do I have to find a regular expression for this language? Or what can I do to check if $L$ is regular or not?
2
votes
1answer
60 views

Are languages regular if their concatenation is regular?

Let $A, B \subset \Sigma^*$ be languages. If the concatenation product $AB$ is regular, are $A$ and $B$ necessarily regular? I'm inclined to think this is true since the regular language $AB$ has a ...
1
vote
1answer
38 views

Is it necessary that X is also regular?

Given that $L$ is a regular language and $X \subseteq L$,does $X$ have to be also regular?
2
votes
1answer
18 views

DFA for {any sequence of a and b, between two consecutive “b” there are maximum 3 “a”}

I have tried to draw a deterministic finite automaton for the language L={any sequence of a and b, between two consecutive "b" there are maximum 3 "a"}: Is it correct?
1
vote
3answers
87 views

NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
1
vote
1answer
48 views

is this language regular or not?

I have problem with this language $$L = \{ a^n b^m : \text{$n+m$ is odd} \}$$ is it regular or not My Solution I used pumping lemma, w = a^2p b^2p+1 (the same for a^2p+1 b^2m ) ...
0
votes
0answers
21 views

reverse of language, decidability

Consider a language L(D) = {w: w and its reverse are in L(D)}. Does reverse of L(D) is the same language ? If so, then consider L = {: M is a DFA for L(D)}, does this make this a turing decidable ...
0
votes
1answer
71 views

Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
1
vote
1answer
82 views

Finding Nerode equivalence classes

How am I supposed to find the equivalence classes of a Language? What should I think? For instance, having a language $$L =\{a^n b^m \mid n,m \ge 0, (m+n) \bmod2=0)\}$$ I can have: $[a^n]$ with ...
1
vote
3answers
54 views

regular language question

Good afternoon everyone; I am stuck with a question I could not find and answer by myself I hope you can help me. My question is The language L = {w : w {a,b}*, |w| is odd, w has exactly one b}. ...
0
votes
1answer
30 views

Is this a regular language? Number of a's greater than $k$

Prove/disprove: $L = \{ w \mid |w|_a \geq 2k \}$, where $\Sigma = \{ a,b\}$ and $k$ is a constant, is a regular language. Intuitively I am saying yes, it is a regular language. But I don't ...
0
votes
1answer
45 views

Show that the language is regular modifying the DFA

Let L be a regular language. How can I show that the language $\text{Suffix}(L)=\{w \in \Sigma^* \mid \text{ there is a $x \in \Sigma^*$ so that }xw \in L\}$ is also regular? How can I modify the DFA ...
1
vote
1answer
106 views

Check if a regex is ambiguous

I wonder if there is a way to check the ambiguity of a regular expression automatically. A regex is considered ambiguous if there is an string which can be matched by more that one ways from the ...
1
vote
0answers
32 views

Why every regular language is in $\text{TIME}(n)$?

How can I prove that every regular language $R$ has linear time complexity, i.e. every regular language satisfies $$R \in \text{TIME}(n)$$
1
vote
1answer
166 views

DFA for Boolean Formula

Let $ f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
1
vote
1answer
21 views

Language regularity implications

I have to decide whether this implications are true or false and prove it. Will you help me? $L.\{a,b\}^{*}$ is regular $\implies$ $L$ is regular $L.\{a,b\}^{*}$ is not regular $\implies$ $L$ is not ...
4
votes
0answers
66 views

Applying the Myhill-Nerode Theorem

Consider the language $$L=\{x y^{(n)} z y^{(n)} w: x,z,w \in \Sigma^*, y \in \Sigma, z\text{ does not contain }y, n \geq 0 \}.$$ To show that the language is not regular using the Myhill-Nerode ...
0
votes
1answer
69 views

Show that the language is regular without a DFA

How can I show that the language {$w \epsilon$ {$0,1$}$^{*}:$ the word $w$ contains neither the (sub)string $000$ nor $11$} is regular without using a DFA? (Using the closure properties)
0
votes
1answer
55 views

Formal Languages - Prefix on Language

Given a language $L$ over an alphabet $\Sigma$, we say that $u,v \in \Sigma^*$ are prefix equivalent over $L$, denoted $u \sim_L v$, if $uw \in L \iff vw \in L$ holds for all $w \in \Sigma^*$. Is ...
0
votes
1answer
81 views

Pumping lemma-regular language

Show that the language $L = \{w \mid w \in \{a,b\}^{*}\}$ is not regular by using the following version of Pumping Lemma: Let $L$ be the language, which has an infinite number of words, then there ...
0
votes
0answers
25 views

Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?

Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...
0
votes
1answer
34 views

Show that the language is regular

Given a regular language L on the input alphabet Σ, and X a subset of Σ*, show that the language {$w$:$w$ $\epsilon$ L, there is a x $\epsilon$ X so that $wx$ $\epsilon$ L} is also regular. Could you ...
3
votes
1answer
33 views

Irregular $a^nb^n$

We studied in class that regular languages closed under intersection. My question is : if we take the irregular language $L =$ {$a^nb^n : n\geq 0$} and the regular finite language $L' = \{a^3 ...
0
votes
0answers
24 views

productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
2
votes
1answer
50 views

Language concatenation

We learned in class that the regular languages are closed under concatenation (e.g $L_1L_2 =\{ w_1w_2 : w_1 \in L_1,w_2 \in L_2\}$ is a regular language if $L_1$ and $L_2$ are also regular ...
0
votes
1answer
18 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
1
vote
1answer
38 views

Pumping lemma $c^2a^nb^n$

I'm trying to prove that the following language is not regular via the Pumping Lemma. But I don't know, why is my procedure wrong (choosen word is incorrect according to my teacher). $$L= c^+ \cdot ...
4
votes
1answer
669 views

Routing Automaton

Is there a formal proof for the following question? For a DFA $M= (Q,\Sigma,\delta,s,A)$, we extend the function $\delta : Q \times \Sigma^* \to Q$, such that every $w \in \Sigma^* $, ...
1
vote
1answer
67 views

Infinite regular languages

There is a formal proof for the following sentence? For every 2 languages $A,B$, we write A@B if A subset of B and B\A infinite. Prove that if $A,B$ regular languages and A@b, than exists regular ...
1
vote
1answer
77 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
1
vote
1answer
41 views

Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $ Whereas $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite regular language. I ...
2
votes
1answer
47 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
0
votes
1answer
52 views

Determine whether $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ is regular.

Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular. Firstly, I think this language is regular. ...
3
votes
1answer
97 views

reverse automata mininum states

There is a formal proof for the following sentence? For every $k$ there is a DFA (deterministic finite automaton) $M$ with $k+2$ states such that every automaton that accepts the language $L(M)^R$ ...
2
votes
1answer
93 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...