# Questions tagged [regular-languages]

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

1,277 questions
Filter by
Sorted by
Tagged with
81 views

25 views

### How do I prove a language is regular? [duplicate]

I've done a lot of research on this topic, but still don't feel very confident about it. Let's say the example is: For a language L over an Σ, define N(L)={w∈Σ∗: wk∈L for some k∈Σ∗}. Prove that, if L ...
35 views

### Proving right quotient of two languages [duplicate]

I know that if a language $L_1$ and a language $L_2$ are regular, then $L1/L2$ is regular. When we construct a DFA $M'=(Q, \Sigma, \delta, q_0, F)$, for each state $i$ we can make $i$ the start ...
627 views

### complement of a language-nfa

hi i know that the question 5 is true because by definition w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L" but iam really confused ...
62 views

### How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: $w=a^ncb^n$...
31 views

### Can somebody please explain what the pumping lemma is? [duplicate]

I've had multiple lectures on the pumping lemma but still can't grasp exactly what it is...my main questions are as follows What is the pumping lemma for? How do you use it to prove a language is not ...
94 views

### Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
40 views

### $L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular [duplicate]

Use the Pumping Lemma to show that $L$ is not regular: $$L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ...
35 views

### What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
40 views

### Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$

How can I produce an automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only ...
218 views

### prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
15 views

### Proving a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
19 views

### Regualr Expression for C comments [duplicate]

I hope you can help me right now, I am working on lexical analyzer for C language, I am bit confuse bout the regular expression of C style comments. a regex which can handle both single and multiline ...
889 views

### Using the pumping lemma for a proof by contradiction [duplicate]

I'm trying to prove that the set of even-length strings with the two middle symbols being equal cannot be accepted by finite automata. I can explain why it cannot be accepted intuitively, but I'm ...
113 views

### Proving a regular expression is correct [duplicate]

I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979). Specifically, I'm unsure how to justify that my regular ...
21 views

### Pumping lemma with two r languages [duplicate]

I have two questions about how to use pumping lemma for regular languages to show that two languages are not regular. I would appreciate if someone can confirm if my answers make sense, and if not, ...
118 views

### Pumping Lemma for regular language [duplicate]

I have a question to find out that L = {a^(2k)|k>=1} is regular. I know that it is regular set but I was looking to find out if pumping lemma is satisfying or not. So I tried it as - ...
122 views

### Making a regular grammar for this language

I'm trying to make a regular grammar for this language: Where the alphabet is $\Sigma$ = $\{a,b,c\}$ It seemed like it would go well with a right-linear grammar. This may be disastrously wrong, ...
186 views

### Proving $\{xx^R \mid x\in L_1, x^R\in L_2\}$ is context-free

I have this problem: Let $L_1$ and $L_2$ be two regular languages. Show that $L_3 = \{xx^r : x \in L_1, x^r \in L_2 \}$ is a context-free language. I am unsure how to prove that some language is ...
54 views

### Show that a language is not regular by Pumping Lemma [duplicate]

Possible Duplicate: How to prove that a language is not regular? Show that $L_2=\{a^nb^k|n\not= k-1\}$ is not regular by Pumping Lemma.
117 views

### Multiples of n is a regular language [duplicate]

Possible Duplicate: Language of the values of an affine function Let $C_n = \{x\mid x \text{ is a binary number that is a multiple of } n\}$. Show that for each $n$, the language $C_n$ is regular....
211 views

1k views

### Can every single regular expression be translated into deterministic finite automata? [closed]

Can every regex be translated into a DFA? Or only a subset of regular expressions? If so, what is an example of a regular expression that cannot be translated into a DFA?
116 views

### Uniqueness of solution in Arden's theorem

Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ...
215 views

### Could we write $(a+b)^* = (\epsilon + a + b)^+$?

I have read that $L^* = L^+ - \epsilon$, but if we write $(\epsilon + a + b)^+$, is it equivalent to $(a+b)^*$?
2k views

### Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular

I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a ...
41 views

### Is a language regular if a word is in a regular language but the reverse is not?

A1 = { $x|x \in A , x^R \not\in B$} A and B are regular over $\Sigma$ Is A1 regular?
57 views

### “Best” automaton for a regular language

For a given regular language, there are multiple finite automata. How do we determine which one is best?
299 views

### DFA for regular language [closed]

I need to construct a DFA which accepts the following language: $$L = \{w \in \{a,b\}^{\ast}\mid \#_{a}(w) \bmod 3 = \#_{b}(w) \bmod 2\}$$ I have no clue how to solve this issue. Can you please help ...
2k views

### Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset construction ...
108 views

### Infinite sequence of regular languages over fixed finite alphabet

Construct an infinite sequence of regular languages $L_1, L_2 , \ldots$, over the same fixed finite alphabet, such that for every $i ≥ 1$, $L_i ⊇ L_{i+1}$ and $|L_i \setminus L_{i+1} | = ∞$.
197 views

### What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
1k views

### NFA: Regular Language that starts with ab but does not end with ab?

$L = \{x \in \{a,b\}^* \mid \text{$x$starts with$ab$but does not end with$ab$}\}$ I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them ...
1k views

### Left Linear Grammar: How to construct?

I need help constructing a Left Linear grammar for the language $L = \{ a^n b^m c^p \mid n\geq 2, m\geq 3, p\geq 4 \}$ Here is what I have so far, I know : $N = \{S\}$ $T = \{ a, b, c \}$ $P = \{$...
875 views

### Constructing right-linear grammar

Is the grammar $\qquad S \to 1A0A \mid 0A \mid \varepsilon$ a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals. I know $0A$ is right-linear but what about $1A0A$? Trying ...
1k views

### Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
108 views

### Why L' is not regular?

$$L'=\{ww|w\in L\}$$ I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular. How can I give such an example if according to closure ...
463 views

### Regular expression of a language over {a,b} which does not contain substring bbb [duplicate]

I want Regular Expression for language L defined over {a,b} and L does not contain substring 'bbb'. I tried something but could not get proper answer.
309 views

### Why is $\Sigma^*$ concatenated with some language regular?

Let $\Sigma=\{a,b\}$. Why is the concatenation of any language with $\Sigma^*$ always regular? I found a problem where $(a+b)^*$concatenated with $a^nb^n$ was regular?
428 views

### How to prove this language is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma = \{a,b,c\}$. Prove that the following language is regular: $\{w | w \in L \text{ and } w \text{ starts with } abc \}$. I wonder what proof ...
Since every finite language is regular, I'm trying to find how would a DFA for the following language $\{xx^R \mid x \in \{a,b\}^*, |x| = \ell\}$ look like. Would there be one DFA for all words of ...