Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
0
votes
0answers
27 views

Proof that truncation of a regular language is regular [duplicate]

Let $L_1$ be a regular language and $L_2$ any language. I want to prove that the language of $L_1$ truncated by $L_2$ is a regular language, i.e. $$\{w| wx\in L_1 \text{ and } x\in L_2\}$$ is ...
1
vote
1answer
58 views

DFAs are regular languages, but regular languages are closed under concatenation

I have course notes which claim the following two facts: First, DFAs recognize exactly the regular languages. Second, regular languages are closed under union, concatenation, and *. Now I have as an ...
0
votes
1answer
161 views

CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $ S \to Α Β S $ $ A \to S $ $ B \to a B b $
-2
votes
1answer
108 views

Myhill-Nerode to prove a language is non-regular

L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.
1
vote
1answer
176 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a CFG $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap L(G)$ is context free since it is the intersection of a regular ...
1
vote
1answer
84 views

Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
0
votes
1answer
39 views

validation of a pumping lemma proof for regular languages

I have the following regular expression: Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
49 views

Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma

I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying ...
0
votes
1answer
52 views

What is Pumping length for Union of Regular languages?

This is an exam question. For E = {a,b}. let us consider the regular language $L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$ Which one of the following can be a pumping length (the constant ...
0
votes
1answer
1k views

Minimum pumping length of (01)* [duplicate]

Michael Sipser offers the definition: The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p ...
0
votes
1answer
146 views

Is this language with prefix regular?

Is this language regular? ${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$} I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|&...
2
votes
2answers
139 views

Prove that every regular subset of $a^nb^n$ is finite

How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite? I know that every finite language is regular, and it's not true that every regular language is finite. I also know that $...
2
votes
3answers
2k views

Prove or Disprove: an infinite intersection of regular languages is a context-free language

Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$. Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language. I ...
2
votes
0answers
31 views

Regular string relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := ...
1
vote
2answers
115 views

Regular of language of all words of length 3

Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$ I think the above language is regular. A DFA can be used to determine the above language. Am I correct? Is the above language regular?...
0
votes
2answers
87 views

Convert the given NFA to DFA

I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$. First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get $L\...
1
vote
1answer
66 views

Number of equivalence classes

Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$? And for the private case that $L$ is regular, ...
1
vote
1answer
58 views

Why Right-Division of regular language with RE\E language is regualr?

I think I can't understand the meaning of language being decidable. The next case makes no sense to me: Considering I have language L1 which is regular, and language L2 which is in RE\R (in ...
1
vote
1answer
100 views

necessary and sufficient pumping lemma - bounded pumping variant

There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular. According to that lemma: A language $L$ is regular iff $\exists k$, $\forall x\in ...
0
votes
1answer
76 views

Is this language L regular?

Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N} $)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar ...
0
votes
1answer
59 views

Complement of $0^n1^n | n \in \mathbb{N}$

I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 ...
-1
votes
1answer
55 views

How to show that a language is regular

I know that to show that a language is not regular, you are supposed to use the pumping lemma, but I cannot figure out how can I show that a language is regular. How would I show that the following ...
-3
votes
1answer
44 views

Construct regular expression for given language

How to construct regular expression for language L={a,b,c} which contain all words starts with bab and ends with babc?
0
votes
0answers
67 views

Is language bin(n)bin(2^(k+1) n + 1)^R context-free

I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
3
votes
1answer
87 views

Minimum pumping length of concatenation of two languages

there's this small part of my homework that I just can't figure out. Let us denote $p(L)$ as the minimum pumping length of some language $L$. I'm supposed to find two regular languages $A,B$ so that ...
3
votes
1answer
150 views

Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $ L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite ...
0
votes
1answer
30 views

When proving a set is not regular is it enough to prove a subset of it regular?

E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?
0
votes
1answer
31 views

How to define an automata for zig zag concatenation? [duplicate]

I have two DFAs one for language A and one for language B. I'm asked to make an FDA that is the zig-zag concatenation of letters of A and letters of B. This is described by the following: {w: w = $a_1 ...
1
vote
1answer
153 views

Zigzag concatenation of two languages

Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
1
vote
2answers
241 views

Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?

I was given a question and don't really know to solve it. Given a regular language $L$, is the following language also regular? $$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length ...
1
vote
3answers
1k views

$a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?

$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\...
3
votes
1answer
128 views

Why is this language a regular language?

Came across this in a book, and I'm wondering why the following language is regular? $$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$ Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
86 views

Regular expression for a palindrome of finite length?

I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$ I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
70 views

I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean

I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do? I know that $\epsilon$ is the symbol for empty ...
1
vote
2answers
73 views

can more than two arrows point towards the same state from other states in a DFA?

Is something like this possible: You have state A,B,C all pointing towards accepting state D. Is this allowed? Where online can I find a list of rules that define how an automata must be drawn or ...
0
votes
0answers
87 views

Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
2
votes
1answer
116 views

$\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
-1
votes
1answer
817 views

Automata that respect the condition {w|w contains at least two 0s and at most one 1}

we have the alphabet {0,1}. {w|w contains at least two 0s and at most one 1} It tried this: (However I'm not sure if it's correct. If it's incorrect why?)
0
votes
1answer
31 views

I'm trying to understand DFAs is my DFA correct in this question if not why?

I have the following alphat {0,1}. I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0} This is the DFA I came up with.
1
vote
1answer
43 views

How to create a regular expression for this language?

I have a language: $$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$ I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
0
votes
2answers
62 views

Is it possible to design a Turing Machine without extra symbols for this language?

Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?
1
vote
0answers
39 views

$L = \{\alpha^i \beta^j \gamma^k \vert i,j,k \in \mathbb{N}_0, (i=1) \Rightarrow (j=k)\}$

I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me? I alredy found an anwser to the Problem above (...
2
votes
1answer
101 views

Two-way finite automaton: How does the automaton remember the state

I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#...
4
votes
2answers
83 views

Regular language as finite union of periodic sets

Is it true that every regular language can be expressed as a finite union of periodic sets? In other words, if $L$ is regular, then do there exist finite sets $A_1,\dots,A_n,B_1,\dots,B_n$ such that ...
0
votes
2answers
106 views

Is a language regular

Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by $$ L' = \{ \alpha \in \Sigma^* \mid (\...
-1
votes
1answer
39 views

Natural Languages

Can one imply that natural languages can be described by regular grammar? Is that what happens through NPL? Trying to understand the subject of how spoken language can be converted to data and how.
1
vote
2answers
203 views

Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular? Thank you for any input.
1
vote
0answers
49 views

How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
1
vote
1answer
114 views

Prove that a finite language is regular

I want to prove that $L(G) = \{01; 11110; 10101; 000\}$ is regular. Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$? How can I also prove it using a DFA?
1
vote
1answer
74 views

Checking whether union of two languages is regular

How to check if $L = \{c^ka^nb^n \mid k>0 \wedge n\geqslant0\} \cup \{a, b\}^*$ is regular ,where $L_1 = \{c^ka^nb^n \mid k > 0 \wedge n\geqslant0\}$ is clearly not regular and $L_2 = \{a, ...

1
3 4
5
6 7
32