Questions tagged [regular-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

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

Prove\Disprove: If $L_1$ is not a CFL, and $L_2$ is finite, then $L_1 \cup L_2$ is not a CFL.

I am getting ready for finals, and encountered this question in a past assignment. I haven't proved this then and I don't understand how I can prove it now. Prove\Disprove: If $L_1$ is not a Context-...
0
votes
2answers
90 views

Does there exist a set of strings $L \subseteq 1^*$ such that $L$ is an irregular language?

I am currently trying to prove/disprove the following statement from my textbook: Let $1^*$ be the regular language of all strings consisting of only ones. Does there exist a set of strings $L \...
0
votes
0answers
37 views

A set of positive measure

There are 2 notions used as a definition of a positive measure of a set: A set $A\subseteq \kappa$ is positive, with respect to a filter $F$ on $\kappa$, if intersects every element of $F$. For the ...
0
votes
0answers
20 views

How do I convert the following NFA to a DFA?

From my textbook, I am trying to convert the above NFA to a DFA (no solution provided). I went through the steps to convert it and ended up with the following DFA solution: At first glance, I thought ...
1
vote
1answer
21 views

Is the Kleene Star $*$ distributive over concatenation?

I'm currently learning about automata theory and I came across the following question: Given an arbitrary set $L$ of symbols. Is $(L \: \cdot \: L)$* = $L$* $\cdot$ $L$* true, where * refers to the ...
1
vote
2answers
21 views

If L is regular, then $L \setminus \{ \epsilon \}$ is regular.

I need to show that if $L$ is regular language, then $L \setminus \{ \epsilon \}$. I was thinking: If $L$ contains $\epsilon$, then in the FSA the start state is a final state. But by making the start ...
0
votes
1answer
59 views

What is the context-free grammar representing the set of all binary strings that contain at least one $1$ and at most two $0$’s?

Context: I am trying to construct a context-free grammar (CFG) for the set of all binary strings that contain at least one $1$ and at most two $0$’s. My solution: $S \rightarrow A0B0B | B0A0B | B0B0A |...
1
vote
2answers
50 views

What is the regular expression representing all binary strings where no occurrence of 00 is immediately followed by a 1?

I am currently working on constructing regular expressions that match a description of a given set of strings from practice problems in my textbook (no solutions are provided in it). I am trying to ...
0
votes
1answer
19 views

Substring of a regular language

Given some regular language $L$, I need to prove that the language of all the substrings of words in $L$ is also regular: $$ Substring(L)=\{y\in \Sigma^* \mid \exists x, z \in \Sigma^* \text{ such ...
1
vote
1answer
33 views

Show that the class of regular languages is closed under gapping

"Let $\Sigma=\{a, b\} . $ For every word $ w=a_{1} \ldots a_{n} \in \Sigma^{*} $ with $ a_{i} \in \Sigma $ and $ 1 \leq k \leq n $ let $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \...
1
vote
2answers
25 views

Does the Kleene Star allow for n-time concatenation or infinite concatenation of a word with itself?

When describing the Kleene Star, is the following correct: The Kleene Star applied to a word w allows for the word to be concatenated with itself 0 to n times, with n [element] N. where N is the set ...
0
votes
1answer
50 views

Regularity of $w^{|w|}$

Is it true that for every regular language $L \subseteq \{0,1\}^*$, the language $\{ w^{|w|} \mid w \in L \}$ is also regular? It seems to me that it is not regular , so I will try to prove it with ...
0
votes
1answer
28 views

Infinite intersection of regular languages

I need to disprove that an infinite intersection of different regular languages is a regular language, using the fact that the language $\{a^nb^n \mid n\ge0\}$ is not regular. I am trying to define ...
1
vote
1answer
31 views

Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ [closed]

I'm trying to find a CFG for the following language: $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ What I thought about unsuccessfully is the following: $S \rightarrow SASBS \mid SBSAS \mid \...
0
votes
1answer
63 views

Is $L = \{xwyw^r \mid x,w,y \in (a+b)^+ \}$ regular?

$L = \{ xwyw^r \mid x,w,y \in (a+b)^+ \}$ where $w^r$ is the reverse string of $w$. If we take $w = {}$minimum string possible ${} = a$ or $b,$ I think it could be regular Lets say $w=a$, then RE ...
1
vote
1answer
77 views

Showing star-freeness of recursively defined languages

Problem: Define a sequence of languages on $A$, a finite alphabet as $D_0 = 1$ (empty string) and $D_{n+1}= (aD_nb)^*$. Show that each $D_i$ is star-free (for each there is an equivalent star-free ...
1
vote
0answers
17 views

Regular expression generating language {$w: w$ contains at least three $1$s}

I am learning automata. As an answer to following question in my textbook, I came up with this answer. Give regular expression generating language {$w: w$ contains at least three $1$s} $0^*10^*10^*1(...
1
vote
1answer
49 views

Is Shuffling of a regular language regular too?

If $A$ be regular language, How we can prove that $A^{'}$ is regular too? $A^{'} = \{a_{2}a_{1}a_{4}a_{3} ... a_{2n}a_{2n-1} \mid a_{1}a_{2}a_{3}...a_{2n} \in A\}$ Is there any way to prove that even/...
0
votes
1answer
40 views

Proving a given language is not regular

I'm interested in proving the irregularity of some language L, which is defined as follows: $0, 1 \in L$ If $w \in L$, then $w 1^{|w|} \in L$ I tried to prove this using the pumping lemma, using the ...
1
vote
1answer
24 views

Why is this map, considered in the proof of a proposition about commutative equivalence, injective?

In the proof of the following Proposition, the authors consider a map $\pi$ and say it is injective. I don't understand why. Proposition: Let $A=\{a,b\}$, and let $X\subset a^*ba^*$. Then $X$ is ...
2
votes
0answers
43 views

What is the easiest way to determine the list of all strings up to length N accepted by DFA or regular expression?

For example I have the next simple regular expression: (11|0)+ It is clear that size of the set of strings that match with this regular expression is infinite: <...
0
votes
1answer
29 views

Creating a regex from regular language

I need to create a regex from this language: $L = \{w\sigma \mid w \in (\Sigma − \sigma)^*; \Sigma = \{a, b, c, d, e\} ; \sigma \in \Sigma\}$ but I don't understand the logic of this language. If $\...
1
vote
2answers
42 views

Prove the following languages are irregular.

Prove the following language is irregular. $$ \{w^n \mid w \in \{0,1\}^*,\ n ≥ 2 \}$$ I'm trying to prove this with the Pumping Lemma, but I'm kind of confused because $w$ is a language not an ...
0
votes
1answer
34 views

Prove or disprove: Any infinite subset of the language L = {$a^nb^m$ | n = m or n = 2m} has to be non regular

I came across two similar types of questions. The first one being: Prove or disprove: Let L be a language of all the palindromes over the alphabets a,b. Then any infinite subset L1 of L such that ...
0
votes
1answer
64 views

Constructing a DFA for a language

Yesterday I saw there was a discussion of the following problem, which I'm interested in too: Given that L is a regular language, construct a DFA for L-pref, where L-pref is defined as follows: L-pref ...
2
votes
1answer
140 views

How to build a DFA for the given language and prove its correctness? [closed]

Let's say $L$ is a regular language. (reminder: the word $x$ is a $\text{Prefix}$ of the word $w$ if: $w=xy$, for some $y$ $\in$ $\Sigma^*$) $L_{pref} = \{w | \text{ at most $1$ prefix of $w$ is not ...
0
votes
1answer
49 views

$L_1$ is regular and $L_2$ is not. What can i say about their union or intersection?

Given $L_1$ is a regular language and $L_2$ is a non-regular language. $\Longrightarrow$ then $L_1\cap L_2$ (the intersection) is non-regular OR $L_1\cup L_2$ (the union) is non-regular. Is it true ...
0
votes
1answer
50 views

How to provide a regular grammar equivalent to context-free grammar?

I know that a regular grammar needs to be of the form: A -> a A -> aB, or A -> λ (lambda) But I am not sure of the steps needed to create a regular ...
2
votes
1answer
72 views

Represent regular languages and automata having more than 26 symbols in their alphabet

I'm working on regular languages and automata with arbitrary numbers of symbols for their alphabet (maybe more than 26.) So I'm showing the alphabet symbols by $a1, a2, ..., an$. For example a regular ...
0
votes
0answers
34 views

Recursion and Induction when given a Regular Expression and Regular Language

If I'm given 2 regular expressions (3 * 1) * (1 * 3) * , (3 U 1 U 1)*, and strings over Σ = [0 - 9],[A - Z],[a - z] how should I go about proving that the regular expressions match the same language ...
3
votes
1answer
65 views

What's the purpose of the word $w$ in the proof for $ L \in \mathsf{REG} \implies L(\varphi) \in \mathsf{MSO}$ with $L(\varphi) = L$?

I'm taking a lecture where we proved $ L \subseteq \mathsf{REG(\Sigma^*)} \iff \exists \phi \in \mathsf{MSO}$ with $L(\phi) = L$. For the first direction $L \subseteq \mathsf{REG(\Sigma^*)} \implies \...
0
votes
1answer
48 views

$L^2$ = $L$ equality implications for a formal language [closed]

Let's say I have a formal language $L$. I wanted to know which of these three equalities can be derived from the the given fact that $L^2$ = $L$: $L^+ = L$ $L^* = L$ $\varepsilon \in L$ where $L^+$ ...
1
vote
1answer
32 views

questions about the pumping lemma

Below is the Pumping lemma as stated in Automata and Computability by (Dexter C. Kozen) Let $A$ be a regular set. Then the following property holds of $A$: There exist $k≥0$ such that for any string $...
0
votes
0answers
54 views

Describe the language of this regular expression?

Give two strings that can be and two that cannot be generated from $$(b^+a)^* b^* \cup (ab ^ +)^* \cup (ab^+)^* a , \text{if}\ \Sigma = \{a, b\} $$.Describe the language of this regular expression? ...
1
vote
1answer
22 views

Show that $A=\{0^k 1^m 0^n |\text{ }n=k+m\}$ has infinitely many equivalence classes.

Show that $A=\{0^k 1^m 0^n |\text{ }n=k+m\}$ has infinitely many equivalence classes. I'm trying to prove that $A$ is a non-regular language. Alternatively, I could use closure properties - but have ...
0
votes
1answer
26 views

Show that $A=\{0^m 1^n |\text{ }m\text{ is even or }m > n\}$ has infinitely many equivalence classes to prove non-regularity.

Show that $A=\{0^m 1^n |\text{ }m\text{ is even or }m > n\}$ has infinitely many equivalence classes. I'm trying to prove that that $A$ is a non-regular language. Alternatively, I could use closure ...
3
votes
1answer
61 views

Automata | Proving that if $L$ is regular then $L'$ (word in $L'$ is a word from $L$ without the first and the last letter) is regular too.

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let $L$ be a regular language and then let $L'$ be: $L' = \{w \in \Sigma^\star : awb \in L, a \in \...
2
votes
1answer
28 views

Write an NFA with only four states

Let $\Sigma = \{0, 1\}$, consider the language $L = \{111\}$, i.e., $L$ contains a single string with three $1$’s. Give an NFA with $4$ states that recognizes $L$... I am kind of stuck since I can ...
1
vote
1answer
36 views

Prove that the language $A= \left \{ x\in\left \{ 0, 1 \right \}^{*}\mid\#\left ( 0, x \right )= \#\left ( 1, x \right ) \right \}$ is not regular.

I initially tried using the pumping lemma, with little success, albeit I still think it's possible. I've been directed that using the Myhill-Nerode theorem would be optimal, but I'm struggling. I need ...
1
vote
1answer
99 views

Prove or disprove: If $A$ is regular and $B$ is not regular, then $A ∩ B$ is not regular.

I suspect the Myhill–Nerode theorem may come into play, but not certain. If this was a union instead of an intersect, I'm certain it's true. I'm relatively confident that this statement is false and ...
0
votes
1answer
49 views

Prove or disprove: If $A$ is regular and $A ∩ B$ is not regular, then $B$ is not regular.

I suspect the Myhill–Nerode theorem may come into play, but not certain. If this was a union instead of an intersect, I'd be almost 100% sure it was true. I'm relatively confident that this statement ...
2
votes
1answer
123 views

Prove or disprove: If $A$ and $A ∩ B$ are regular, then $B$ is regular.

I suspect the Myhill–Nerode theorem will come into play, but not certain. If this was a union as opposed to an intersect, I'd be pretty confident that this would be true, but with it being an ...
1
vote
1answer
105 views

Prove $\{0^k10^k10^k1 \in \{0,1\}^* \mid k \geq 0 \}$ is not context free

I'm practising for my CS exam and got stuck on this problem $$ \{0^k10^k10^k1 \in \{0,1\}^*\mid k ≥ 0\}. $$ I think I have good start however I don't know how to proceed. I assume the L is context ...
2
votes
1answer
36 views

How to prove $\text{if } {B \subseteq A} \implies A^*B^* = A^*$

For context, A and B is a regular language, and related to Theory of Computation. As the title says, it is so intuitive that $$ \text{if } {B \subseteq A} \implies A^*B^* = A^* $$ I don't know how to ...
1
vote
0answers
35 views

How can I prove that this language is context free?

How can I prove that this language is context free, where $A$ and $B$ are regular languages ? $$L= \left \{ wx\mid w\in A, x\in B \right \}$$
1
vote
1answer
55 views

Pumping Lemma works on language, but language is not regular

So i am given this language: L = { $c^ma^nb^n $ | $m≥ 1 $ and $n≥ 0$ } U { $a^mb^n$ | $m,n≥ 0$ } And i have to prove that the pumping lemma property works on L. Although pumping lemma can work, i then ...
2
votes
0answers
24 views

$w = 0001000 \in L'$, but this $w$ is not in $L$?

Suppose if $L ⊆ Σ^∗$ is a regular language then the following language is also regular: $$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$ For a simple example, let L be given by the regular expression $...
0
votes
1answer
40 views

Kleene Star over a formal Language containing Unions

I am a little bit confused, how the following language should be understood or further more, how the Kleenestar is interpreted in some ways: $ ( \{0\} \cup \{1\}^*)^*$ I think the language looks like ...
0
votes
0answers
22 views

Use a proof by contradiction that for any A⊆Σ*, the concatenation A∅ = ∅.

I want to know how to prove with contradiction that for any A is a subset of a finite set, then the concatenation of A∅ = ∅.
1
vote
2answers
37 views

Notation Confusion (Specifically: “Such That”, & Multiple $\exists$)

There are a couple of notation-related matters that I find myself clumsily working around quite often when writing proofs, and I was hoping for some help with dealing with them: Let's say that $L$, $...

1
2 3 4 5
23