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 ...
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 ...
0
votes
1answer
32 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'...
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
3answers
94 views

Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma. I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
1
vote
1answer
98 views

Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
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 ...
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
2answers
93 views

Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
1
vote
1answer
45 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
1answer
206 views

building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$ I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
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 ...
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
vote
2answers
78 views

Are regular grammar languages defined from "accepting" states?

In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
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
2answers
52 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 ...
0
votes
2answers
76 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
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 ...
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
60 views

Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
-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
888 views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
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....
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
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)...
0
votes
1answer
74 views

Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$

I'm trying to simplify the following REGEX: $$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$ $R$ is the result of transforming a GNFA that recognizes $L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|...
1
vote
1answer
263 views

Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
-1
votes
1answer
51 views

Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS: $$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$ But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful. Any ideas?
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
45 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 ...
-1
votes
1answer
68 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 ...
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
131 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 ...
-1
votes
1answer
61 views

Prove language is not Turing-recognizable using contradiction

Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ...
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 ...
2
votes
3answers
91 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
0
votes
3answers
233 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{ ...
36
votes
6answers
6k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-...
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
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
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
33 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
44 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 \...
0
votes
2answers
113 views

Kleene star operations

Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages. a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$. b.Let $\Lambda \...

1
2 3 4 5
33