Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,853
questions
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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-...
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.
...
-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: ...
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? ...
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 ...
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$.
...
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 \...
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 ...
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 ...
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 ...
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 ...
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.
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.
-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 ...
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:
...
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 ...
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 ...
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\...
-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 ...
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 ...
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(...
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 ...
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 ...
-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 ...
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, ...
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 ...
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 ...
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 ...
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 (...
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{...
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-...
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, ...
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 $...
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 ...
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 ...
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$, ...
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 ...
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 ...
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,...
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 ...
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 ...
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, ...
-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 ...
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 ...