Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0 votes
2 answers
109 views

Language to regular expression to prove it is regular

I'm trying to find a regular expression to describe the following language: $\{a^n xa^n | n≥1,x ∈ Σ^* \}$ where $Σ$ = {a,b} So far I've come up with $aa^* (aUb)^* aa^*$ but I don't think that accounts ...
moonraker's user avatar
  • 103
0 votes
1 answer
75 views

Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language

I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $>$ and $\geq$ symbols when ...
80s's user avatar
  • 1
0 votes
1 answer
63 views

Exists and forall in formal language definition in the case of kleene star [closed]

Let's suppose we have language $Y = \{a^ib^j:i,j \in N^*\}$ defined over the alphabet $\Sigma^{}_{} = \{a, b\}$ If we want to define this language $\Sigma^{*}_{}$ \ $\ Y$ such that we don't have the ...
V_head's user avatar
  • 33
0 votes
0 answers
71 views

Grammar for prime length strings

How do we write an unrestricted grammar for $$L = \{a^n \ | \ n \ \text{is prime}\}$$ I know that $L$ is neither regular, nor context-free. Also, I know how to build a Turing Machine for $L$. The idea ...
muser's user avatar
  • 150
0 votes
1 answer
31 views

Determining class of language with pumping lemma?

I have the language $L = \{ 0^{2l} 1^m | l,m >= 0 \} \ where \ \Sigma= \{0,1\} $ which I am trying to find the class of language for, e.g. not context-free, context-free, regular. By this notion I ...
S.web's user avatar
  • 3
0 votes
2 answers
99 views

Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$

Description This is an exercise for Formal Language course, I'm asked to find a grammar for language: $L = \{ 0^i1^ic0^j1^j | j = i+1 \}$ As an example: 01c0011 can be generated using this language, ...
Morphlng's user avatar
1 vote
0 answers
58 views

minimum number of non-terminals so that for all context-sensitive languages there is a non-contracting grammar

Every context-sensitive language $\subseteq \Sigma^* = \{a,b\}^*$ can be expressed using an essentially non-contracting grammar. With just one non-terminal symbol, we can't express all context-...
user126100's user avatar
0 votes
1 answer
96 views

Is my DFA optimal?

I designed this FSM graph to demonstrate a DFA that would accept any string that is of length 5, must contain a d, can only have as and/or bs before the d, and can only have bs and/or cs after the d. ...
242342345's user avatar
  • 103
-2 votes
1 answer
256 views

Proof for Language: L1 ∪ L2 ⊆ L1L2

I have a question for my thesis research, but I am not able to find proof of this. Does anyone have any idea on what should be approach be in order to prove this? Question: ...
Victoria Ed's user avatar
1 vote
1 answer
81 views

Minimal-length strings which are substrings of no string in a given CFL

Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? ...
breandan's user avatar
9 votes
4 answers
2k views

Non-regular language whose prefix language is regular but not the whole set of words

I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of ...
user6767509's user avatar
0 votes
1 answer
38 views

Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?

I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution. My approach was that it has infinite because, lets say we have $x = a^5$ and $y = a^7$. ...
tomato's user avatar
  • 17
1 vote
2 answers
85 views

Show for every $CFL$ $L$ that's not $REG$ exists $L_1,L_2$ with $L_1$ is $REG$ and $L_1 \subseteq L_2$ and $L_2$ is not $REG$ and $L \subseteq L_2$

i want to show that for all $CFL$ and not $REG$ languages $L \subseteq \{0,1\}^*$ exists $L_1,L_2\subseteq\{0,1\}^*$ with: $L_1$ is $REG$ $L_2$ is $CFL$ and not $REG$ $L_1 \subseteq L_2 $ $L \...
tomato's user avatar
  • 17
0 votes
0 answers
301 views

proof that there exists a regular expression r for every NFA with only 2 states

Let L be a regular language. Then there exists a regular expression r such that L = L(r). Proof for NFAs with only 2 states (can be generalized!), partly seen during a lecture and completed by me: Let ...
Ronald's user avatar
  • 89
0 votes
1 answer
278 views

Suppose we have an empty alphabet Σ=∅, what are the possible languages of this alphabet?

Lets say the alphabet is Σ=∅,what are the possible languages of this alphabet? According to my definitions: I know that an alphabet is a finite set of symbols Σ I know words is a set of all finite ...
MohG's user avatar
  • 3
0 votes
0 answers
119 views

proof that halting problem is undecidable

In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301, there is a proof for the fact that the halting problem is undecidable. The proof ...
Ronald's user avatar
  • 89
1 vote
1 answer
193 views

pumping lemma length restrictions clarification

I know that this kind of question has been asked before, but I still see different kind of answers getting multiple upvotes, but I am not sure if they are all correct. That’s why I wanted to ask it ...
Ronald's user avatar
  • 89
1 vote
1 answer
68 views

Is LR(1) closed under union?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
2 votes
0 answers
50 views

Is LR(1) closed under concatenation?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 L_2$ (their concatenation) guaranteed to also be LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
-1 votes
1 answer
314 views

Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word

Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word accepts if and only if there are exactly 2 accepted paths and all the others reject or no ...
ATB's user avatar
  • 135
0 votes
2 answers
123 views

Is $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ context free?

i have seen this question where someone was asking if $\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$ is context free. Then there was an answer that says that it is context free because: ...
tomato's user avatar
  • 17
0 votes
1 answer
77 views

How to recognize all halting states of a turing machine?

Given a turing machine with some states, how can I recognize all halting states of that machine? I think that I should go over each state and check if there is a transition that is not defined for ...
Ronald's user avatar
  • 89
2 votes
1 answer
74 views

minimal DFA transition function clearification

Statement: Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense ...
Ronald's user avatar
  • 89
0 votes
1 answer
274 views

Extended transition function in NFA

The following statement seems trivial, but how can it be formally proven/argued? $$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\...
Ronald's user avatar
  • 89
-2 votes
1 answer
154 views

Is $L=\{\langle M_1,M_2\rangle|L(M_1)\cap L(M_2)\neq \emptyset \}$ R, RE or coRE?

Below is the language, determine (R), (RE), (coRE). and prove your answer. $L=\{\langle M_1,M_2\rangle|M_1,M_2$ are Turing-machines and $L(M_1)\cap L(M_2)\neq \emptyset \}$ Attempt: I Think the ...
Protes's user avatar
  • 1
1 vote
2 answers
101 views

Optimal way to construct union automata of two DFAs

Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the ...
Ronald's user avatar
  • 89
0 votes
1 answer
95 views

proving a step in the proof of regular intersection

Let $L_1$ be a context-free language and $L_2$ be a regular language. Then $L_1 \cap L_2$ is context-free. Part of a proof given in the book "Formal languages and automata": Let $M_{1}=\left(...
Ronald's user avatar
  • 89
0 votes
1 answer
107 views

Greibach Normal Form: Proof every sentential form is of the form xy with x terminals and y variables

For any grammar in Greibach normal form, every sentential form obtained from S by a partial left-most derivation is of the form xy with x terminals and y variables. I think that this can be proven ...
Ronald's user avatar
  • 89
0 votes
0 answers
34 views

Power of regex extensions [duplicate]

It is well known that classical regexes recognize exactly regular languages. But in practice, many programming languages have extensions to the regex syntax which potentially broaden the field of ...
user7427029's user avatar
-1 votes
1 answer
47 views

Pumping lemma for context-free languages: Importance of length restriction

(from 'An Introduction to Formal Languages and Automata' by Peter Linz) What I do not understand, is why we have done our best to make sure that the condition (8.2) holds. Why is this restriction ...
Ronald's user avatar
  • 89
2 votes
1 answer
141 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
Toothpick Anemone's user avatar
0 votes
1 answer
101 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
Toothpick Anemone's user avatar
4 votes
1 answer
142 views

Formal grammar of MIU system

The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules: Xi → Xiu mX → mXX XiiiY → XuY XuuY → XY and a start axiom "mi" I have tried to find a formal ...
Ctx's user avatar
  • 143
1 vote
1 answer
202 views

prove that there does not exist a Turing machine with a particular property

Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite. The above question ...
Fred Jefferson's user avatar
0 votes
1 answer
94 views

Transition System vs State Machines

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
Jahid Chowdhury Choton's user avatar
1 vote
2 answers
348 views

How to disambiguate CFG with unary/binary minus and binary prefix operator

I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1). I'm facing the current fragment of the language: $$ \begin{...
Jonas Kölker's user avatar
1 vote
1 answer
388 views

determining whether a context-free language is regular

I was wondering how to determine (with proof) whether the context-free language generated by the following context-free grammar $G$ is regular, where $S$ is the start variable and $a$, $b$ are the non-...
Fred Jefferson's user avatar
1 vote
1 answer
42 views

if $RA$ is context-free, is $A$ context-free?

If $RA$ is context-free for a regular language R, is $A$ context-free? I think this statement is true. Let G be the CFG given by the rules $S_0\mapsto LA_1, S\mapsto LA_1, A_1\mapsto SA_2 | RS | 1, ...
Fred Jefferson's user avatar
0 votes
0 answers
92 views

How to prove reverse of DFA?

How does one formally prove that, given a DFA $M=\langle Q,T,\delta,q_0,F\rangle$, the following NFA $M^R = \langle Q_R, T, \delta_R, q_R, F_R\rangle$ recognizes the reverse of M's language? We build $...
Pablo M's user avatar
  • 99
0 votes
1 answer
59 views

prove that the unique language $A$ such that $AB$ is context free for all languages B is the empty set

Prove that the unique language $A\subseteq \Sigma^*$ such that $AB$ is context free for all languages $\subseteq \Sigma^*$ is the empty set. If $A$ is not the empty set, there should be a way to ...
Fred Jefferson's user avatar
1 vote
1 answer
60 views

What complexity class is this?

Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question. Disclaimer 2: All corrections to this question are ...
Qwerty Boy's user avatar
1 vote
1 answer
514 views

Prove a subset of a regular language is regular, context-free but not regular or not context free

I've been tasked with solving this problem, but I'm not sure where to begin: Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, ...
Eatay Mizrachi's user avatar
1 vote
0 answers
264 views

show that neither $S$ nor $\overline{S}$ is turing recognizable

Let $S = \{\langle M\rangle | M \text{ is a TM and } L(M) = \{ \langle M\rangle\}\}$. Prove that neither $S$ nor $\overline{S}$ is Turing-recognizable. I think the statement can be proved via a ...
Fred Jefferson's user avatar
0 votes
1 answer
726 views

Prove that the language of all Turing machines that accept finitely many words is decidable or not

Question: we have the following language: $$A = \{\langle M \rangle :| L( M)| < \infty \text{ and } M\text{ is a Turing machine}\}$$ where $\langle M\rangle$ is the encoding of $M$ and $L(M)$ is ...
ArithEgo's user avatar
1 vote
1 answer
34 views

Nonexistance of collection of 'transformers' that 'trivially modify' Turing machines?

For a given recursive language $L$, let $TL$ be the language of turing machines that accept $L$, for some encoding of turing machines. $TL$ is countably infinite. Does there exist a set $S = \{S_1,S_2,...
QCD_IS_GOOD's user avatar
2 votes
1 answer
163 views

Formal language rewrite rules: strange notation

I'm reading "Program=Proof" by Samuel Mimram, and they use a notation for defining a formal language that I'm not familiar with. Here is how "Program=Proof" defines a formal ...
Evgenia Karunus's user avatar
1 vote
1 answer
250 views

How are regular languages not structurally recursive?

This blog posting states that "regular languages aren't structurally recursive" while "That's not the case for context-free grammars" In what sense is the term "structurally ...
user3414663's user avatar
1 vote
3 answers
447 views

How to prove the language of words $a^ib^jc^k$ where $\min(i,j)\le k\le\max(i,j)$ is not context-free?

I want to prove that $\mathcal M =\{a^ib^jc^k \mid \min(i,j)\le k\le\max(i,j)\}$ is not a CFL. Using the pumping lemma, let $p$ be the constant, then I choose $w=a^pb^pc^p$. When I separate to cases, ...
Math4me's user avatar
  • 249
-2 votes
1 answer
67 views

Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
Math4me's user avatar
  • 249
1 vote
1 answer
149 views

variable repetitions in pumping lemma for context-free languages

Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz. The picture below is in support of the proof. I do not ...
Tryer outer's user avatar

1 2 3
4
5
58