The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
29 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
226 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
30 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
48 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
37 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
16 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
62 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
40 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
18 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
57 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
47 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
53 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
27 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
44 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
70 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
30 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
147 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
59 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
64 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
51 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
70 views

Pumping lemma-regular language

Show that the language L={ww:w $\epsilon$ {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 are ...
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
32 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
31 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
22 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
49 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
17 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
35 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
665 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
65 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
74 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
45 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
93 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
81 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 ...
1
vote
1answer
93 views

Possible solution for Sipser 1.63

Sipser's question 1.63: Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets. Is my solution correct? Since $A$ is infinite and ...
1
vote
1answer
49 views

Divide $x=123456$ into three factors $x=uvw$ such that $uv^iw$ is divisible by 3

I have the problem of dividing the string 123456 into three factors uvw that such $uv^iw$ as a number is divisible by three, where $\left|uv\right|\le4$ and $\left| v\right|>0$, i.e. the factors u ...
1
vote
0answers
45 views

$DFA/NFA$ for $L(OPPOSITE)=\{uv:vu\in L\}$

I'm trying to prove that: $L(OPPOSITE)=\{uv:vu\in L\} \in L_{FA}$ given that: $L \in L_{FA}$ . I'm trying to construct a finite automata that accepts $L(OPPOSITE)$ in order to prove it but I got ...
1
vote
1answer
36 views

If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular?

I've encountered a question during my studies: If $L\cdot\{\epsilon,0\}$ regular language, is $L$ regular? I thought to disprove it by using $A\subseteq 2\mathbb{N}, L=\{w\in\{0\}^*:|w|\notin A\}$ ...
1
vote
1answer
39 views

Complement of a Set of Strings in a Language

Suppose $B= \{ 0^n1^m2^{n-m}:\, n\ge m\ge 0 \}$ Is the complement $\overline B = \{ 0^n1^m:\, 0\le n\lt m\}$? Or is it the universe of all possible strings (including all strings with symbols ...
1
vote
0answers
30 views

Constructing a Turing decidable machine from DFA

I am a trying to prove that every regular language is decidable. So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine. ...
0
votes
1answer
37 views

Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
1
vote
1answer
55 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
0
votes
1answer
39 views

Pumping Lemma - Clarification of Usage

I'd like to make sure my understanding of the Pumping Lemma is correct. Consider $L=\{ 0^n1^m2^{n-m}:\, n \ge m \ge 0\}$ I'm going to give 2 solutions to prove that $L$ is not regular. One using ...
0
votes
1answer
62 views

Context Free Language [Prove Or Disprove]

Given the language below: $$L = \left\{w\in (a + b + c)^*: n_a(w) = n_b(w)\text{ or }n_a(w) \ne n_c(w)\right\}$$ How would I prove or disprove that it is either context free. I know that if it was ...
0
votes
1answer
62 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 ...
3
votes
2answers
41 views

Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
0
votes
1answer
93 views

induction to prove regualr expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...