Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
0
votes
3answers
4k views

NFA or DFA for strings the contain exactly twice substring ab?

Given the language with alphabet: $\{a, b, c\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody ...
1
vote
1answer
1k views

Regular expression for the language where every a is surrounded by b's

I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b ...
0
votes
1answer
3k views

Can a Turing Machine decide only non-regular languages?

I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular language....
2
votes
1answer
4k views

Is the class of non-regular languages closed against Kleene star?

How to prove that if a language A is not regular then A* isn't regular either? I have tried the usual methods with no result.
-1
votes
1answer
2k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
3
votes
3answers
1k views

Metrics and algorithms for complexity of a graph

I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short ...
1
vote
1answer
128 views

Does a language stay regular if you re-encode the input? [duplicate]

$\tau$ be a transformation that, applied to a word of $\Sigma_a^\star$, replaces each character with a word from a possibly different $\Sigma_b^\star$ and concatenates the resulting words. For ...
2
votes
1answer
223 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
1
vote
1answer
93 views

Prove language is not regular? [duplicate]

I know how to use the pumping lemma to do so, but I don't think that can be used for this language: $$L = \{x \in \{0,1\}^* : \text{no prefix of $x$ has more $1$'s than $0$'s}\}. $$ What other ...
1
vote
1answer
58 views

Which grammar is this?

Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the ...
5
votes
1answer
348 views

Undergrad resources for identifying regular languages with Myhill-Nerode matrices

I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure ...
1
vote
0answers
25 views

How to show that a languge is not regular [duplicate]

How can I show that this language is not regular? $$ L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \} $$ This is my attempted solution: Assuming the pumping number to be $p$ and making $m=0$ ...
2
votes
2answers
562 views

Recognizing finite state machines with repetition

I'm interested in finite state automata which have the capacity to require repetition. That is, the machine may be in a state in which the next character may be any character from set $S$, but, ...
0
votes
3answers
3k views

How to prove every context-free language over a unary alphabet is regular?

How can I show that every context-free language over a unary alphabet is regular?
2
votes
1answer
917 views

DFA / NFA Regular Languages

Consider the non-deterministic finite automaton A: (in below figure) 1> convert this NFA to DFA 2> Find if there are equivalent states of your DFA 3> Minimize the DFA of <2> if possible This is ...
1
vote
1answer
40 views

Removing constant symbols from language to prove irregularity

I'm confused about a solution I saw about the following language not being regular:\begin{equation*} L=\{0^n ~1 ~2^n : n >0\} \end{equation*} The example solution said that $L$ was "the same as":\...
1
vote
2answers
341 views

Is this pumping lemma proof correct?

$$ L = \{a^ib^jc^k \mid i,j,k > 0 \text{ and } i+k>j\} $$ I say it's not regular. Proof by pumping lemma: Find a string $xy^iz$ that is not in $L$ (respecting the constraints). Let $w=x^py^pz^p$...
3
votes
1answer
522 views

Where in the Chomsky Hierarchy are Regular Expressions as a language?

I'm referring to regular expressions as language: \begin{equation*} \Sigma = \{ ``a", ``b", ``(", ``)", ``*", ... \} \end{equation*} and \begin{equation*} L = \Sigma^* \text{, which form a legal ...
41
votes
0answers
2k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
2
votes
1answer
4k views

Regular expression for a string not containing a set of substrings

I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure ...
0
votes
0answers
123 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, ...
3
votes
2answers
4k views

Are regular languages closed under inverse homomorphism?

Let $\Sigma$ and $\Delta$ be alphabets. Consider a function $\varphi: \Sigma \rightarrow \Delta^*$. Extend $\varphi$ to a function from $\Sigma^* \rightarrow \Delta^*$ such that: \begin{eqnarray*} \...
0
votes
1answer
206 views

NFA and DFA storage cost

In some paper I read, A theoretical worst case study shows that a single regular expression of length $n$ can be expressed as an NFA with $O(n)$ states. When the NFA is converted into a DFA, ...
2
votes
0answers
98 views

Pumping a Language does not imply regular [duplicate]

I am currently studying the pumping lemma for regular languages and I am trying to come up with an example where even if the language can be pumped it is not regular. Which condition of the lemma ...
0
votes
1answer
997 views

Class of the language of Turing machines that loop on at least one input

$L = \{ \langle M \rangle \mid \text{there is at least one input string on which the \(M\) does not halt} \}$ Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, ...
6
votes
1answer
218 views

Characterising $(aa)^*$ in first order logic

In my descriptive complexity class, we've been asked to find a formula that characterises the language $(aa)^*$ (over the alphabet $\{a\}$) with a first order formula over the language $\{<, P_a\}$....
0
votes
1answer
391 views

If $M$ recognizes an infinite language, then $M$ has a cycle [closed]

An NFA $M$ contains a cycle if there is a state $q$ and a string $x$ such that if $M$ is in state $q$ and reads string $x$, $M$ can return to state $q$. Prove: If $M$ recognizes an infinite language, ...
2
votes
0answers
12k views

Is the class of non regular languages is closed under complementation?

This is the question I am asked and I am currently proving it using proof by contradiction something like this: Let's take some language L which is non regular. Let's assume compliment of L i.e. $(L^...
2
votes
2answers
1k views

Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma: $L= \{0^n 1^m \space | \space m \equiv 0 \...
0
votes
2answers
175 views

Proving that a derived language is regular [duplicate]

Suppose I have a DFA recognizing a regular language $L$, how do I prove that $$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular ...
-2
votes
1answer
205 views

Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as: X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }. Prove that if X is context-...
-2
votes
2answers
1k views

Prove or disprove whether L is regular [duplicate]

Let $\Sigma = \{0,1\}$. For every word $w \in \Sigma^*$, let $|w|_0$ and $|w|_1$ denote the count of 0's and 1's, respectively, in $w$. Let $L$ be the language $$L = \{ w \in \Sigma^* \mid |w|_0 \gt |...
3
votes
2answers
2k views

What is a regular expression that matches all strings over the alphabet except a particular substring?

I've come across this problem in my studies, and I've abstracted it to the more general case here. Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, ...
3
votes
1answer
2k views

Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular? [duplicate]

Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$ is also regular? I have a 'feeling' that ...
3
votes
3answers
219 views

Decide if L is regular or not and argue it. Trying to use Pumping Lemma

Part (a): Let $L = \{x \in \{0,1\}^* \mid \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$. So I want to use the ...
4
votes
2answers
2k views

Determine if this language is regular

Let $L = \{xyx \mid \text{ for some }x,y \in \{0,1\}^+\}$. Is this language regular? So I was trying to construct a DFA, but I don't how to do this with this language.
1
vote
1answer
72 views

Concatenation among different language types

I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be ...
4
votes
1answer
210 views

Finding two words of lengths that are relatively prime in a regular language?

Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$. How to decide whether there are two words $w,w' \in L$ such that the length of $w$ is relatively prime to the length of $w'$ ?
5
votes
4answers
18k views

Designing a DFA that accepts strings such that nth character from last satisfies condition

This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
2
votes
3answers
155 views

Why is this language regular?

If you could include your thought process in determining why it's regular it would help me a lot. $L_1 = (0^*(10)^*11)$ $L_2 = \{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all ...
5
votes
2answers
222 views

Why is this language involving reversal regular?

For a language to be regular it needs to be recognized by DFA/NFA. Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$. $x^r$ means the reverse of $x$. A DFA has no ...
1
vote
2answers
124 views

Show that A** subset of A*, where A is a regular language

I do not understand the proof for this. I know that every word in $(A^*)^*$ is made up of words from $A^*$, and that this is made up from words in $A$. But how does this help with showing that $(A^*)^*...
4
votes
3answers
5k views

Is the language that accepts strings concatenated with their reverse regular?

If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\...
7
votes
1answer
162 views

Results on the languages recognized by undirected DFAs

For my Bachelor's thesis, I consider the class of languages recognized by symmetrical DFAs, that is, deterministic (complete) finite automata satisfying the following condition: Let $A$ be a ...
2
votes
2answers
246 views

Measures and probability in formal language theory

I am looking for references for the following problem: I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in ...
13
votes
1answer
354 views

Finding maximal factorization of regular languages

Let language $\mathcal{L} \subseteq \Sigma^*$ be regular. A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with $X \cdot Y \subseteq \mathcal{L}$ $X \neq \emptyset \neq Y$...
0
votes
2answers
5k views

How can a Turing Machine recognize a regular language?

This is a practice problem for a midterm in a class I'm taking: Given a regular language $L$, describe formally a Turing machine that recognize $L$. I'm not sure how I should do that.
18
votes
1answer
564 views

Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an ...
3
votes
3answers
2k views

Are regular and context free languages closed against making them prefix-free?

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...
-2
votes
2answers
501 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.

1
26 27
28
29 30
32