Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
68 views

Prove a language created by applying a function on a regular language is regular

Let $L$ be a language over $\Sigma=$ {$a,b,c$} We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$. Let $T(L)=${$ T(w) : ...
  • 306
2 votes
1 answer
36 views

Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?

Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable? I think that $L$ is not $\...
3 votes
1 answer
613 views

Can we transfer every DFA to DFAs with start state having no in edge?

The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
1 vote
1 answer
63 views

Transform a non-regular language into a regular one using sort

Is there a way where sort turns a non regular language into a regular one. What I mean by sort is this: Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively. ...
3 votes
0 answers
49 views

Reference request about equivalence of automata / regular expressions up-to a language

The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can ...
1 vote
1 answer
102 views

Regularity or non-regularity of union of two languages

Consider this language: $K=\{xy \mid x=\{a,b\}^*, y=x^R \text{ or } y=x\}$ I know that these languages are non-regular separately: $K_1=\{xy \mid x=\{a,b\}^*, y=x^R\}$ $K_2=\{xy \mid x=\{a,b\}^*, y=x\}...
0 votes
1 answer
49 views

Is pumping lemma not applicable for every 'long enough' string in the language?

I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
  • 15
-1 votes
0 answers
25 views

If A is nonregular, then there exists a nonregular language B such that A∩B is infinite

Please provide a short, high level proof if the above statement is True, and a counter example if the statement is false.
1 vote
1 answer
33 views

Is it true that $R.L^* + L^* = R + L^*$?

I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further. I want to ...
  • 15
0 votes
1 answer
44 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
0 votes
0 answers
27 views

Pumping length of (a+b)(a+b)*

I'm trying to figure out the pumping length of (a+b)(a+b)* From what I understand, this means that there is some A or B followed by any number of either A's or B's e.g ABBBB or AAAAA but AAAABA ...
1 vote
1 answer
25 views

Confusion regarding FLEX(regular expressions)

I am building an analyzer that takes in text and numbers the lines; taking in hello how are you i'm fine thanks as input and using the code: ...
  • 11
0 votes
0 answers
53 views

What is a regular expression that describes whether an integer w is a multiple of 6?

Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
1 vote
1 answer
91 views

How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?

Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row. Let $\Sigma_2 = \left\{ \begin{bmatrix}0\\ 0\end{bmatrix}, \begin{bmatrix}0\\ 1\end{...
  • 11
1 vote
0 answers
19 views

Extending minimal top-down tree automata

I'm trying to find an algorithm to update minimal top-down tree automata/hypergraphs. Regular tree grammars can be seen as definitions for recursive data structures: ...
  • 111
0 votes
1 answer
62 views

Operation of non-regular with regular language

Would it be correct to say that on a operation with a Non-regular language (L) with a Regular language will always return the language L? I'm came across a property that when we intersect a non-...
  • 115
1 vote
0 answers
27 views

Which non regular language meets the requirements for pumping lemma for regular languages?

I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
0 votes
0 answers
13 views

Converting regular expression to WS1S formula

Is there a "textbook" procedure to convert a regular expression such as $((0,1)(1,0))^*$ to a formula in WS1S?
  • 2,230
0 votes
1 answer
40 views

Does every regular expression describe only 1 language?

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it Also, $...
-3 votes
1 answer
37 views

prove $a^nb^m; n<3m + 2$ is not regular by the pumping lemma

I want to prove this language $a^nb^m; 0 \leq n< 3m+2$ to be not regular by the pumping lemma. This is my attempt, is this a correct way of doing it? Let's suppose $L$ is regular. Let $s = a^{3k+1}...
-2 votes
1 answer
31 views

regular languages under intersection and union, a bit of confusion to clarify

Let's assume that $L_1 = a^nb^{2n}$ and $L_2 = a^na^{2n}$, knowing that $L_1$ is not regular, and $L_2$ is. We also know that regular languages are closed under intersection and union, and complement. ...
0 votes
1 answer
35 views

prove $a^nb^nc^m; n,m \geq 0$

I proved this language $L = a^nb^nc^m; n,m \geq 0$ is not regular the following way: Let $L \cap a^*b^* = a^nb^n$ We know that $a^nb^n$ is not regular, and $a^*b^*$ is regular. Thus, if $L$ is ...
1 vote
2 answers
103 views

Prove $a^nb^{n^2+n}$ is not regular by the pumping lemma

I want to prove this language $L=\{a^nb^{n^2+n}:n\in\Bbb N\}$ to be nonregular by the pumping lemma. This is my attempt, is this a correct way of doing it? Let's suppose $L$ is regular. Let $s = a^kb^{...
0 votes
1 answer
52 views

If $L_1 \cup L_2 \in RE$ does it implicate that at least one of them is also in RE?

This was one of my exam questions and the answer is apparently no. Can someone explain why because I don't understand.
  • 11
1 vote
1 answer
76 views

Is the equivalence problem of a CFG and a FSM decidable?

I have the following problem: Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
-2 votes
1 answer
30 views

Is a^n , n = 3j+4k , n>=0, a context-free language?

I have no idea how to approach this question... How would I go about proving or disproving this? any explanation is appreciated.
  • 1
0 votes
0 answers
29 views

Is a^n b^k , 0 <= n <= k^2, a context-free language?

I don't think it's a CFL, but I'm having a hard time using the pumping lemma to prove this. Is there any way I can use homomorphism? Maybe h(a)= a, h(b) = lambda... If the pumping lemma is more ...
  • 1
1 vote
1 answer
50 views

Is $L = \{a^{p^2}\mid p\text{ is a prime}\}$ regular?

By pumping lemma, we choose the word $w=a^{p^2}$ that the decomposing is $[a^sa^ta^{p-s-t}]^p$ such that $u=a^s,v^i=a^t,x=a^{p-s-t}$ $[a^sa^{it}a^{p-s-t}]^p=[a^{p+it-t}]^p$ We choose i=p+1,we get $ [a^...
0 votes
1 answer
27 views

How to make a recursive definition for a given predicate?

I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression: $r=\emptyset$ $r=\varepsilon$ $r=a:\...
0 votes
1 answer
44 views

Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
1 vote
1 answer
39 views

Check whether a regular expression is correct

I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct? ...
  • 150k
0 votes
1 answer
34 views

Regular grammar such that it rejects keywords

I want to write a regular grammar that follows the C language. I almost wrote the grammar, but was not able to resolve how to define a variable. Def: A variable can be any combination of characters, ...
  • 1
0 votes
2 answers
105 views

If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?

L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1. Is L1 regular under the property that regular languages are closed ...
0 votes
1 answer
203 views

Using the pumping lemma, show that L = {a b^n c^n | n ≥ 0} is not regular

I've encountered many examples which its format is like: a^n b^n. For this I understand that w = 2n and is pretty straightforward, but what happens in my case? Is w = 1 + 2n? And in this case would |...
0 votes
0 answers
36 views

Complement of a language definition

Let $A=\{$ M is a TM, $s\in \mathbb{N}$ and $\exists x\in\Sigma^*$ s.t M rejects $x$ in at most $s$ steps $\}$. I want to define its complement, so how do I negate "$\exists x\in\Sigma^*$ s.t M ...
  • 37
4 votes
0 answers
71 views

Inverse operation to concatenation for regular languages

I'm currently in need of the inverse operation of the concatenation of 2 regular languages. Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
0 votes
1 answer
45 views

Why must 2 distinct strings go to the same state in a DFA?

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA. Is it that if there are n words and m states, where there are more ...
0 votes
3 answers
77 views

Proving L1 ∪ L2 ⊆ L1* L2*

I'm stuck here, how can i prove this: $$L_1 \cup L_2 \subseteq L_1^*L_2^*$$ $$\begin{array}{rcl} x\in L_1\cup L_2 & \Rightarrow & x\in L_1^* \lor x\in L_2^*\\ &\Rightarrow &x\in L_1^*\...
1 vote
1 answer
49 views

Shuffle of a DCFL and a regular language

This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability". The shuffle $A||B$ of two languages $A$ and $B$ is defined as $\{w \mid w = a_1b_1\ldots a_kb_k,$ ...
  • 13
0 votes
2 answers
73 views

Regular language under intersection and complement confusion

I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as ...
  • 33
0 votes
2 answers
68 views

Language to regular expression to prove it is regular

I'm trying to find a regular expression to describe the following language: $\{a^n xa^n | n≥1,x ∈ Σ^* \}$ where $Σ$ = {a,b} So far I've come up with $aa^* (aUb)^* aa^*$ but I don't think that accounts ...
  • 103
2 votes
1 answer
35 views

How to prove that for any words $w_1, ..., w_n$ of alphabet $\{0,1\}$ regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?

How to prove that for any words $w_1, ..., w_n$ on alphabet $\{0,1\}$ the regular expression $w_1^*w_2^*...w_n^*$ doesn't represent language $\{0,1\}^*$?
0 votes
1 answer
73 views

Are all non-context-free language infinite?

Are all non-context-free language infinite?
  • 1
0 votes
1 answer
62 views

Show that the the language $L = \{0^kww0^m | k,m \ge 1, w \in \{0, 1\}^*\}$ is nonregular

Caveat. You have to show this specifically by showing there exists an infinite set that is pairwise distinguishable with respect to L. This question was on a quiz which we had 12 minutes to complete (...
0 votes
0 answers
28 views

Show non regularity of a language using closure property

Show that the language $\{0^n1^m0^n| m,n\in \mathbb{N}\}$ is not regular using closure properties. I tried showing this using pumping lemma but I am stuck when it comes to closure properties. Please ...
  • 1
0 votes
1 answer
27 views

How to use BNF for {a^n b^n | n>0}

so I know that this language is not regular, however, can you still define the language using BNF? This is the problem: {a^n b^n |n>0}
0 votes
0 answers
23 views

Regular expression for strings that do not contain the substring $aa$ and contain an even number of $a$'s [duplicate]

I am trying to find the regular expression for the set of strings over the alphabet $\{a,b\}$ that: do not contain the substring $aa$ and contain an even number of $a$'s Such examples include: $...
0 votes
1 answer
64 views

Is my DFA optimal?

I designed this FSM graph to demonstrate a DFA that would accept any string that is of length 5, must contain a d, can only have as and/or bs before the d, and can only have bs and/or cs after the d. ...
  • 103
0 votes
1 answer
48 views

Regular Language to Regular Expression

Let's assume I have the following regular language: L = {1,0}*{010}{1,0}* I would like to convert this to regex for a program. Would the equivalent regular expression for this be: ((0+1)*(010)(0+1)*) ...
9 votes
4 answers
1k views

Non-regular language whose prefix language is regular but not the whole set of words

I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...

1
2 3 4 5
35