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

Is that a regular express? Proof using closure properties or pumping theorem [duplicate]

I am studying regular express. I understand how to proof a xa ya. However, I don't know how to proof the below problem. Please help me. L = { xa yb | a ≠ b }
0
votes
1answer
2k views

Is (a+b)* and (ab)* same in finite automata?

Regular language of (a+b)* and (ab)* are: (a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...} (ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... } I am new to Finite automata and this simple notion is ...
4
votes
2answers
168 views

Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
0
votes
2answers
82 views

What does this language notation specify?

I am given this exercise: Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2. w1=ε w2=aabbcc w3=abbccw w4=aabbcccc w5=...
1
vote
2answers
67 views

Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

I am trying to show that $A = \{w \in \{a,b,c,d\}^{*}|w \textrm{ has equal occurences of } ab \textrm{ and } cd\}$ is not regular by using the Pumping Lemma. My idea here was to use the string $ s = (...
1
vote
1answer
42 views

Applying the Pumping Lemma to aspecific string

Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$...
0
votes
2answers
32 views

string concatenation vs language concatenation

What exactly is the difference between $$ C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\} $$ and $$ D = \{a^nba^nba^nb | n \geq 0 \} $$ It is known that D is non-regular and C is regular, but I am not sure ...
2
votes
2answers
100 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
0
votes
2answers
50 views

Read regular Expression from NFA

Good evening everyone! Can someone help me with the following task? So we have this NFA: I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
1
vote
1answer
228 views

What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as $(0+0001)((1111)^*+(00)^*)$ What is the length of the longest string ...
2
votes
1answer
44 views

Is “A -> aAA” convertible to regular grammar?

I have a simple grammar as below and wonder if it is convertible to regular grammar? If yes, what is the conversion sequence? If no, how can we prove it? ...
0
votes
1answer
80 views

minimum number of states in cross product of two minimum DFAs

If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
0
votes
1answer
52 views

Proving of regular language [duplicate]

Is this regular or not L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
1
vote
2answers
215 views

How to prove that concatenating a language A and A* is commutative?

Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far. If $A$ is ...
0
votes
0answers
112 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
6
votes
2answers
2k views

Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
2
votes
3answers
82 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 ...
1
vote
1answer
26 views

A regular language derived from another

This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular: $$ \{x|\exists y \; |y| = 2^{|x|} ...
0
votes
1answer
62 views

Can this language be called regular?

Recently, I was facing some problems in effectively proving the following : Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
2answers
137 views

How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
1
vote
1answer
38 views

Regularity of a language constructed from a know regular language

I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language: $$ \{x|\...
0
votes
2answers
108 views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular. If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
0
votes
1answer
51 views

How to apply Arden's theory to determine a regular expression

If $P=ab$ and $Q=a^*$, how do I use Arden's theorem to determine the regular expression $R$. I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
1
vote
1answer
65 views

Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
0
votes
2answers
43 views

Can a regular expression be any string from the language described by it? [closed]

Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
2
votes
2answers
63 views

Proving non-regularity via syntactic congruence classes?

Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation: $$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$ One ...
3
votes
0answers
63 views

BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1
vote
1answer
391 views

Check if a NFA accepts a string of non-prime length

Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number. My ...
0
votes
0answers
31 views

Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
1
vote
1answer
63 views

How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma

Here the problem is that I’m confused how to take the pumping value $p$ is it arbitrary any value? Also I don’t know if I should prove all $3$ conditions of the pumping lemma is false or if any one ...
3
votes
1answer
55 views

Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1

A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) star-height of a generalized regular expression is the maximal ...
0
votes
1answer
73 views

What language does this deterministic finite automaton accept?

Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
3
votes
2answers
343 views

Proof that L^2 is regular => L is regular

I'm trying to show $L^2 \in \mathsf{REG} \implies L \in \mathsf{REG}$ with $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right. I first tryed to show $L \in \...
4
votes
1answer
198 views

Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

I try to show that this language is regular: $L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
0
votes
1answer
135 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
0
votes
0answers
46 views

Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
0
votes
1answer
191 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$ ...
2
votes
1answer
44 views

Prove that the language is not regular through Myhill-Nerode Equivalence

The language is given by: $$L=\{a^nb^m|n<m\}$$ I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence. Any help ...
1
vote
0answers
60 views

Is every language described by a grammar?

I read the following argument showing that not every language is described by a grammar: For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
0
votes
2answers
89 views

Proof that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular

Prove that $L=\{a^ncb^n| n \in \mathbb{N}\}$ is not regular. Here is my try, I would really appreciate if someone could tell me if this is a correct proof. Proof: Lets assume L is regular. Then we ...
1
vote
0answers
57 views

Number of words of length n for special language

Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties: if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
1
vote
2answers
83 views

Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
3
votes
1answer
174 views

If $A$ is context-free then $A^*$ is regular

I am currently studying for my exam and I am having trouble to solve this question: Right or wrong: If $A$ is context-free then $A^*$ is regular. I think it's wrong because if $A$ is context-free it ...
0
votes
2answers
752 views

Is checking if regular languages are equivalent decidable? [duplicate]

Is this problem algorithmically decidable? L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2? I think that it is decidable because you can write regular expressions for each ...
1
vote
2answers
85 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 ...
5
votes
0answers
99 views

Growth function for non-regular languages

For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence ...
0
votes
0answers
33 views

Proof that truncation of a regular language is regular [duplicate]

Let $L_1$ be a regular language and $L_2$ any language. I want to prove that the language of $L_1$ truncated by $L_2$ is a regular language, i.e. $$\{w| wx\in L_1 \text{ and } x\in L_2\}$$ is ...
1
vote
1answer
70 views

DFAs are regular languages, but regular languages are closed under concatenation

I have course notes which claim the following two facts: First, DFAs recognize exactly the regular languages. Second, regular languages are closed under union, concatenation, and *. Now I have as an ...
0
votes
1answer
182 views

CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $ S \to Α Β S $ $ A \to S $ $ B \to a B b $
-2
votes
1answer
116 views

Myhill-Nerode to prove a language is non-regular

L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.

1
3 4
5
6 7
32