Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,715
questions
0
votes
1
answer
51
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.
...
- 103
-1
votes
0
answers
19
views
Language for the the set of strings with no more than two consecutive a’s [duplicate]
I need to define a basic language for the set of strings with no more than two consecutive $a$’s over $\Sigma = \{a,b\}$.
Does this look correct?
$L = (\{b\} \cup \{ab\})^* \cup ((\{b\} \cup \{ab\})^* ...
- 1
0
votes
0
answers
24
views
How to translate Python's For loop into operational semantics?
I've spent hours, struggling to understand the basics of operational semantics. In a couple of resources and videos that I've reviewed, one of the most intuitive example that I found was the ...
- 1
0
votes
1
answer
66
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: ...
- 101
1
vote
1
answer
28
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? ...
- 113
9
votes
4
answers
1k
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 ...
- 381
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$.
...
- 7
-2
votes
0
answers
37
views
All finite languages are regular languages, are all regular languages finite?
my thought pattern here to $L=\{a^* b^*\}$ which is countably infinite, and regular (we can construct a DFA that is accepting) so therefore NOT all regular languages are finite...
0
votes
2
answers
53
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 \...
- 7
0
votes
0
answers
42
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 ...
- 89
0
votes
1
answer
60
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 ...
- 3
0
votes
0
answers
64
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 ...
- 89
1
vote
1
answer
115
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 ...
- 89
0
votes
1
answer
48
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.
- 19
1
vote
0
answers
31
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.
- 19
-1
votes
1
answer
38
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 ...
- 135
0
votes
2
answers
70
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:
...
- 7
0
votes
1
answer
49
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 ...
- 89
2
votes
1
answer
69
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 ...
- 89
0
votes
1
answer
22
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\...
- 89
-1
votes
0
answers
25
views
$L=\{<M>|M$ is a TM that halts on at most one input$\}$ class the L in $R, RE, coRE$
Classify the language if in with class the L in $R, RE,coRE$ and prove your answer
$L=\{<M>|M$ is a TM that halts on at most one input$\}$
I think $L\in coRE$, $L$ is similar to the language ...
-2
votes
1
answer
29
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
1
vote
2
answers
47
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 ...
- 89
0
votes
1
answer
80
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(...
- 89
0
votes
0
answers
28
views
Find a context free grammar for $0^n10^m1$, where n is even and m is odd
Let $$L_1 = \{0^n10^m1 | n, m \in N \text{ where n is even and m is odd} \}$$
I tried to build a cfg but I am not sure if it right or if it is the simplest solution.
$$ G_1: V = {S}, T = \{0, 1\}$$ ...
- 211
0
votes
1
answer
42
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 ...
- 89
0
votes
0
answers
27
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 ...
- 111
-1
votes
1
answer
40
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 ...
- 89
2
votes
1
answer
39
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, ...
- 149
0
votes
1
answer
37
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 ...
- 149
0
votes
0
answers
22
views
What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?
In computer programming, there are many different ways to write a for-loop.
Some examples are shown below:
...
- 149
4
votes
1
answer
96
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 ...
- 143
0
votes
0
answers
18
views
Is this Pumping Lemma proof correct? L = {{ca^ndb^m | n >= m >= 1}
Let L be = {ca^ndb^m | n >= m >= 1}
Let x be the word = ca^nd^m with |x|= 2n>=n. Look at x = uvw with |V|>=1 and |UV|<=n.
We have u= ca^kdb^k, v= b^l, w=b^m-k-l with |v| >= 1 and |uv|...
- 1
1
vote
1
answer
26
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 ...
- 279
0
votes
1
answer
22
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
50
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{...
- 689
1
vote
1
answer
62
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-...
- 279
1
vote
1
answer
27
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, ...
- 279
0
votes
0
answers
39
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 $...
- 99
0
votes
1
answer
30
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 ...
- 279
1
vote
1
answer
34
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 ...
- 23
1
vote
1
answer
53
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$, ...
- 113
0
votes
0
answers
57
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 ...
- 279
0
votes
1
answer
69
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 ...
- 5
1
vote
1
answer
29
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,...
- 113
0
votes
0
answers
35
views
Can the leaf nodes of a parse tree be labeled by a variable, a terminal, and the empty symbol; or only a terminal and the empty symbol?
When you are deriving a string using a context-free grammar (CFG), you
start with the start symbol and at the right side you have combinations of
variables (non-terminals) and terminal symbols.
Let's ...
- 345
2
votes
1
answer
123
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 ...
- 184
1
vote
1
answer
75
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 ...
- 111
1
vote
3
answers
143
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, ...
- 241
-2
votes
1
answer
47
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 ...
- 241