Questions tagged [regular-languages]

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

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

Show that L(P) is a regular language by constructing a FSM M such the L(M) = L(P)

I am practicing random CFG problems. I have the following problem which is very confusing for me. Can somebody help me on how to approach this problem. Let $P = (K,\Sigma,\{\}, q_0,\Delta, F)$ be a ...
0
votes
1answer
32 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
votes
0answers
18 views

Mealy Machine That Doubles a Binary

So I was trying to do a mealy machine that doubles a binary. But you know if you want to double a binary, you shift it to left once or add zero at the end. So this image is the one that divides by 2 ...
-3
votes
0answers
10 views

Finding out the language generated by a context-free grammar

how can i find out the language that accepted by this cfg : S -> A B | B C A -> B A | x B -> C C | y C -> A D | x D -> y
1
vote
0answers
52 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
39 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
36 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
26 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
110 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
23 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
227 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{ ...
0
votes
1answer
23 views

Understanding about pumping lemma for regular language-confusions of beginner-:

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 ...
-2
votes
0answers
52 views

Regular grammar for language that does not contain "abab"

I tried this : $V = \{S,A,B\}$ and $T = \{a,b\}$. $S \rightarrow aS | \epsilon | abaAS | BS$ $A \rightarrow a | aA$ $B \rightarrow bB | \epsilon$ Any thoughts/objections?
1
vote
1answer
29 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
42 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
562 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
49 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$ ...
-2
votes
0answers
16 views

How to choose splits in pumping lemma to prove language not regular

I am confused how we choose $0\;^{n-p}$ 1 and $0^n$ What's the logic going on here?
1
vote
1answer
40 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
32 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
43 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
61 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
38 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
41 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
62 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
37 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
62 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
47 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
57 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
24 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
50 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
135 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
62 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
46 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
51 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
48 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
40 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
0answers
35 views

Prove that the language such that the concatenation of any string with its complement is accepted by a regular language is regular [duplicate]

I’m trying to solve the following question: Suppose you have a regular language L with the alphabet {0,1}*. Show the language L’ = {x : x x_c \in L} is also regular. x_c is the flipped version of x ...
4
votes
2answers
74 views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
1
vote
1answer
72 views

I have found an example where regular expression is not closed under concatenation. Where am I wrong?

$a^n$ is a regular expression. $b^n$ is a regular expression. their concatenation is $a^nb^n$ which is not a regular expression.
0
votes
1answer
46 views

Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
2
votes
1answer
56 views

Implication of the Pumping lemma

I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
1
vote
2answers
63 views

Can a non-deterministic finite automaton die out before reading the entire string?

I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by: However, my problem is: If the ...
2
votes
2answers
120 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
1
vote
0answers
88 views

Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states

Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...

1
2 3 4 5
32