As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
-1 votes
0 answers
18 views

Pumping lemma about regular language

I need to test if this language is regular using pumping lemma L = {x ∈ {0,1}* | ∃y ∈ {0,1}* . xxx=yy} So, this is the language of strings with three equal chars ...
Camel2Camel's user avatar
0 votes
0 answers
15 views

Theory of computation

I am trying to look answer for this question of toc please help me find the answer. The question is : Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
Amy's user avatar
  • 1
0 votes
1 answer
22 views

Is the language of sums of integers regular?

Over the alphabet $\Sigma=\{0,\ldots,9,/\}$, is the following language regular: $$L=\left\{x/y/z:z=\mathrm{str}\bigl(\mathrm{int}(x)+\mathrm{int}(y)\bigr)\right\}$$ where $\mathrm{str}$ maps an ...
John's user avatar
  • 103
0 votes
0 answers
18 views

What is the reversal of a regular language useful for?

There is a number of questions on this website about the reversal of regular languages: Closure under reversal of regular languages: Proof using Automata Proving that the reversal of a language ...
John's user avatar
  • 103
2 votes
2 answers
38 views

Can you enumerate the set of all words over a finite alphabet?

Can you enumerate the set of all words over a finite alphabet?
AAAAA5555555's user avatar
1 vote
1 answer
36 views

Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$

Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$. Let our alphabet be $\{0,1\}$, with non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$. The other ...
ShyPerson's user avatar
  • 911
2 votes
1 answer
62 views

Does my finite state automaton accept a string iff it contains the given string as a substring?

I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
ZarakshR's user avatar
  • 125
0 votes
1 answer
24 views

Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$

Preliminaries. Let $n,m,p \in \mathbb{N}$ with $n,m,p > 1$. We allow that $p$ could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \{0,1\}$, with non-...
ShyPerson's user avatar
  • 911
2 votes
2 answers
69 views

Counting States in the trim automaton for $L\circ L'$

Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
ShyPerson's user avatar
  • 911
1 vote
1 answer
51 views

Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$

To understand the Pumping Lemma, I'm going to prove that the language $L = \{0^n1^m0^n | n,m \geq0\}$ is not regular. I choose string $w = 0^{p/2}1^{p/2}0^{p/2}$, for any even number $p$. Clearly $|w| ...
M a m a D's user avatar
  • 1,509
0 votes
1 answer
53 views

Example of L not regular language that suff(L) is regular

I can't find example of L not regular language that suff(L) is regular I tried something like this: {0^n1^n|n>= 0}, but i can't prove that it's suffix is regular Suff(L) = {x ∈ Σ ∗ | ∃u ∈ Σ ∗ such ...
user1701057's user avatar
0 votes
1 answer
37 views

Check if these 2 regular expressions are equivalent

Check if these 2 regular expressions are equivalent: $R_1 = (a+b)^*(aa+bb)$ $R_2 = (a+b)^*aa+a^*bb+b^+b$ My approach: We check if both of these expressions generate the same set of strings. Meaning ...
RandomGuyOnMath's user avatar
0 votes
0 answers
58 views

Proving a certain language is regular by constructing a DFA

Let $L$ be a regular language over the alphabet $\sum$, prove that the language defined by $\hat{L} = \{uv \in \sum^* | u^Rv \in L \}$ is regular. There is guidance in the exercise that instructs us ...
Yarin's user avatar
  • 129
0 votes
1 answer
43 views

CFG for the given language L = { a^l a^n b^m c^m d^n e^l | l,n,m>=0 }

I am writing this CFG to solve the problem: S -> ASBSC A -> aAe | ε B -> aBd | ε C -> bcC | ε Is this correct or not
Yousaf's user avatar
  • 1
0 votes
1 answer
27 views

Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?

The options are: (a) $L \cap a^{\ast}b^{\ast}$ (b) $(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$ (c) $L \cup a^{\ast}b^{\ast}$ (d) $(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$ My doubt is: We ...
Pratik Hadawale's user avatar
2 votes
1 answer
36 views

Is there a algorithm to determine if a regular language (expression) is subset of another?

Given two regular languages (fx given by it's accepting regular expression), is there an algorithm to determine if one is a subset of the other?
skyking's user avatar
  • 123
1 vote
2 answers
54 views

Deterministic infinite automaton equals a normal DFA?

Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA. Attempt ...
NitayStack's user avatar
0 votes
0 answers
33 views

Desgining NFA under certain constraints

I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
Yarin's user avatar
  • 129
0 votes
1 answer
79 views

Designing a DFA with nth character condition for any integer n

Let n be an integer. How can I write finite automata for the language L? L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}. (Please suggest answers; not hints.) Attempt Using Regex, I ...
NitayStack's user avatar
1 vote
2 answers
84 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) : ...
Aishgadol's user avatar
  • 316
2 votes
1 answer
39 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 $\...
Jerry Tao's user avatar
3 votes
1 answer
625 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 ...
Pouya Kafashi's user avatar
1 vote
1 answer
77 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. ...
Anonymous's user avatar
3 votes
0 answers
51 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 ...
Martin Berger's user avatar
1 vote
1 answer
106 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\}...
Birborian's user avatar
0 votes
1 answer
53 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 ...
Axo's user avatar
  • 115
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 ...
Axo's user avatar
  • 115
0 votes
1 answer
47 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 ...
Alan Whitteaker's user avatar
0 votes
0 answers
33 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 ...
GuestPersonOnThisShow's user avatar
1 vote
1 answer
26 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: ...
AlexG's user avatar
  • 11
0 votes
0 answers
61 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 ...
Anonymous123's user avatar
1 vote
1 answer
106 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{...
Patrick's user avatar
  • 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: ...
Taren's user avatar
  • 111
0 votes
1 answer
65 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-...
h4kr's user avatar
  • 115
1 vote
0 answers
31 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?
SmallBrainStudent's user avatar
0 votes
0 answers
17 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?
user1868607's user avatar
  • 2,230
0 votes
1 answer
42 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, $...
Pratik Hadawale's user avatar
-3 votes
1 answer
43 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}...
Papa's user avatar
  • 1
-2 votes
1 answer
32 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. ...
Papa's user avatar
  • 1
0 votes
1 answer
39 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 ...
Papa's user avatar
  • 1
1 vote
2 answers
163 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^{...
Papa's user avatar
  • 1
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.
ReyM's user avatar
  • 11
1 vote
1 answer
93 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(\...
sockaddr's user avatar
-2 votes
1 answer
32 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.
emrb99's user avatar
  • 1
0 votes
0 answers
30 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 ...
emrb99's user avatar
  • 1
1 vote
1 answer
51 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^...
Mostfa Mostfa's user avatar
0 votes
1 answer
29 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:\...
David Krell's user avatar
0 votes
1 answer
51 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 ...
Aamod Thakur's user avatar
1 vote
1 answer
49 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? ...
D.W.'s user avatar
  • 152k
0 votes
1 answer
36 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, ...
NIKHIL's user avatar
  • 1

1
2 3 4 5
36