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
15 views

A regular expression E* defines an infinite language $L_E$ [closed]

So I'm studying for an exam which is about languages and automata. There is a question in the book which asks us to prove that given a regular expression that can be infinite, say $E*$, the language ...
-1
votes
0answers
16 views

Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$

Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$. Hello, I have been trying to solve this problem, my intuition tells that ...
1
vote
0answers
8 views

Contiguous-substring operator

If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
0
votes
1answer
33 views

Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free

Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free. Hi I'...
4
votes
1answer
62 views

$\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises. $L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
1
vote
1answer
47 views

Describing the language of this Automaton

I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
0
votes
0answers
16 views

Could I have used PL directly on this language instead of proving it the way I did? [duplicate]

In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$. I have already solved this by ...
0
votes
1answer
25 views

Which z should I pick?

I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
1
vote
1answer
35 views

Proving irregularity of $a^{k!}$ using Nerode's theorem

Use Nerode's theorem to prove that the following language $L$ is not regular: $$ L=\{a^{k!} \mid 1\leq k\} $$ Here is my attempt: Let $A$ be an infinte set of words s.t- $$ A=\{a^n \mid n\in \mathbb{...
1
vote
1answer
31 views

Problem with Understanding Pumping Lemma

I'm trying to solve this exercise that asks to determine whether a language is regular or not. Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ...
0
votes
0answers
26 views

PDAs with bounded stacks accept regular languages [duplicate]

I've been trying to solve the following problem from Martin's Introduction to languages and the theory of computation, 4th edition: Suppose that $L \subset \Sigma^{*}$ is accepted by a PDA $M$. ...
0
votes
1answer
57 views

I want to determine if this language is non regular-any tips?

After working through some examples of proving the non-regularity of languages I encountered this language $$ L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\} $$ Where $a^{k}$ = a repeated k times....
-1
votes
1answer
47 views

Is the right quotient of a regular language respect to another regular language a regular language?

Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
0
votes
1answer
47 views

How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$ I don't know how many $a's$ should I push into the stack when reading $a$, and how many $a's$...
1
vote
0answers
60 views

Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
0
votes
1answer
42 views

Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?

I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$ Is this language regular or not? My solution Using ...
1
vote
2answers
46 views

Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular [duplicate]

I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular These are all the facts I have been able to gather ...
0
votes
1answer
33 views

Can any language be expressed by regular expression?

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &...
2
votes
0answers
132 views

Proving that a specific Turing machine accepts a regular language

Calling all math buffs! ;) A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank ...
0
votes
1answer
26 views

Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
0
votes
1answer
22 views

Can a non-regular language have a regular grammar?

Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now: S -> 1 | 0 | ε Since it ...
0
votes
3answers
234 views

Can the diagonal language be empty?

We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ ...
1
vote
1answer
43 views

Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

I want to understand how is this proof working. What I know: Pumping lemma for regular language-: Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every ...
0
votes
1answer
33 views

Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
0
votes
2answers
54 views

Check Proof Using Pumping Lemma to Show Language Not Regular

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular. I'll state the pumping lemma here for clarity: Pumping lemma If $A$ is a regular ...
3
votes
2answers
578 views

Regular Expressions - What is difference between a+ and a⁺

I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
0
votes
1answer
51 views

Prove that $\{xyz \mid zyx \in A \}$ is regular if $A$ is regular

Does the following work and is there anything possibly simpler? Let $X = (Q, \Sigma, \delta, s, F)$ be a DFA for $A$. Intuitively, we want to "remember" (or guess) two states $p$ and $q$ ...
1
vote
1answer
50 views

Dividing a String According to the Pumping Lemma

I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He ...
2
votes
0answers
34 views

Summary of Pumping Lemma Application

For my own understanding I would like to summarize how to use the pumping lemma to show that a language is not regular. The pumping lemma is defined as follows. Pumping lemma If $A$ is a regular ...
0
votes
1answer
46 views

Need help with constructing a DFA

I am trying to construct the DFA that accepts the following language $$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
1
vote
1answer
22 views

How to show closure of regular languages without DFA,NFA,reg expressions

Given a $\Sigma$ I define a regular language as one of the folllows: $\emptyset$ $\left\{ \sigma \right\}$ for any $\sigma \in \Sigma$ $L_1 \cup L_2$ for regular $L_1, L_2$ $L_1 \cdot L_2 $ for ...
1
vote
1answer
37 views

The Closure Of Regular Language Under Reordering Alphabets

For a regular language $A$ with the alphabet $\{a, b\}$. Is $L$ a regular language, where $L$ contains strings of $A$ but sorted with $a$ and $b$? In other words, formula: $L = \{ a^{\#_a(x)}b^{\#_b(x)...
-2
votes
2answers
76 views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
0
votes
1answer
46 views

Prove the class of regular languages is closed or not closed under the operations below

Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
0
votes
1answer
56 views

Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
-1
votes
1answer
69 views

Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language

Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ...
1
vote
2answers
43 views

What is the minimum pumping lemma length of $01^*0^*1$?

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
2answers
77 views

Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
0
votes
0answers
58 views

If $L$ is regular, is $L/w = \{x\mid wx\in L\}$ regular?

I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular. It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ ...
2
votes
2answers
58 views

If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
1
vote
1answer
26 views

Regular expression for all a* except aa?

I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable: a aaa aaaa aaaaa ... It's for part of the below DFA
0
votes
0answers
55 views

Whether $L(G)=L(R)$ is decidable for DCFL and CFL?

Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not? My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
2answers
163 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
1
vote
1answer
70 views

Why equality is decidable for regular language but not for $CFL?$

There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
48 views

Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]

We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
144 views

Adding a finite set to a non-regular language

Suppose $A = \{0^{n}1^{n} \mid n \ge0\}$, which is not regular, and let $B$ be a finite subset of $\Sigma^* \setminus A$. Is $A \cup B$ regular?
1
vote
1answer
52 views

Difference between (0)* and (0*)*

I know that, 0* generates, NULL, 0, 00, 000, 0000, ... and so on. But how does (0*)* ...
0
votes
1answer
53 views

How to convert this regular grammar into a finite state automaton?

In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac. The ...
1
vote
1answer
23 views

Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
1
vote
2answers
51 views

Irregularity of $\{a^p : p \text{ prime}\}$ using Myhill–Nerode

Consider the language $$ L = \{2^k : k \text{ is prime}\}. $$ This language contains, for example, $2^3=222$, $2^5=22222$, $2^7=2222222$, and so on. I know that $L$ is irregular and so there must ...

1
2 3 4 5
33