Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
81 views

What is the regular expression of this language? [duplicate]

$\Sigma = \{0, 1\}$ $L = \{x$| $x \in \Sigma^* $ $\&$ $ \#_0(x) = 3$ $or$ $ \#_1(x) = 3 \}$ What is the regular expression of this language? At first I thought $r = (0+1)^*0(0+1)^*0(0+1)^*0$ $...
0
votes
0answers
15 views

Struggling with Pumping Lemma application [duplicate]

I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ...
0
votes
0answers
90 views

Proving that $\{0^nw1^n\mid n\geq 0, w\in\{0,1\}\}$ is irregular [duplicate]

How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.
0
votes
0answers
51 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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$...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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\}$ ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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 - ...
0
votes
0answers
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, ...
0
votes
2answers
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 ...
0
votes
0answers
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.
0
votes
0answers
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....
-1
votes
2answers
211 views

Prove that languages which contain words whose lengths are multiples of a constant are regular

This is a problem involving the theory of regular languages. I am stuck on this problem and do not know how to solve this type of problem. Prove that the language $B_n = \{ a^k \mid k \text{ is ...
-1
votes
1answer
337 views

Prove Language Is Union of Fninitely Many Arithmetic Progressions [closed]

So, you see in the image the question and its answer (proof below the black line). I get the entire proof until the last formula. It basically says that if length of a string is larger than number of ...
-1
votes
2answers
2k views

Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA

$L = \{a^i b^j a^k \ | \ k > i + j\}$ Use the pumping lemma to show that this language cannot be accepted by an FA. Proof: Suppose $L$ can be accepted by an FA. Suppose a string $s = xyz \...
-1
votes
2answers
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?
-1
votes
2answers
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 ...
-1
votes
3answers
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)^*$?
-1
votes
2answers
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 ...
-1
votes
1answer
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?
-1
votes
1answer
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?
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
2answers
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} | = ∞$.
-1
votes
1answer
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 ...
-1
votes
2answers
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 ...
-1
votes
1answer
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 = \{$...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
2answers
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 ...
-1
votes
1answer
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.
-1
votes
1answer
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?
-1
votes
1answer
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 ...
-1
votes
2answers
2k views

Find a DFA for a finite set of palindromes

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 ...
-1
votes
1answer
119 views

Confusion in Pumping Lemma

I would like to know whether we could pump $ba$ into $bbba$ where x=$b$,y=a,z=$\epsilon$ using the finite state machine given in the image 1. For example as given in this image 2 where the string $...
-1
votes
1answer
199 views

Proving that a programming language is not regular

I am wanting to show that the C programming language is not a regular language. The alphabet would be ASCII characters and comments, strings, char can contain arbitrary characters. Would I best ...
-1
votes
1answer
477 views

checking if string is generated by regular grammar

How do I check wether a string is generated by given regular grammar? I know you can check for it in O(N), what is the algorithm called?
-1
votes
1answer
181 views

Language of Palindrome-Prefixed Words

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of: Regular but not Context-Free Context-Free but not Regular Decidable but ...