Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,888
questions
1
vote
1
answer
27
views
Detect (indirect) left-recursion in a context-free grammar?
Given a context-free grammar:
A -> α0 | α1 | ...
B -> β0 | β1 | ...
...
It's straightforward to determine whether the grammar is directly left-recursive - it ...
- 151
0
votes
0
answers
37
views
A term equation
Let $t,a$ are some terms in a first-order language, $x$ is a free variable,
the notation $t[x:=a]$ denotes the rezult of replacement in $t$ every occurrence of $x$ with $a$.
Suppose, we have a term ...
- 101
2
votes
2
answers
466
views
Do all instances of a given string get replaced under a rewrite rule?
I am doing a course in uni on Automata and Formal Languages, and I think I've come across a pretty significant misunderstanding. When you have a rewrite rule in a grammar, and apply it to a string, do ...
0
votes
1
answer
48
views
Is the difference between an unrecognizable language and a finite language decidable? recognizable?
Given 2 languages, A and B, such that A is not turing recognizable, B is finite, is it true that A-B is necessarily not turing recognizable?
I am studying to an exam and would appreciate your help! I ...
4
votes
1
answer
58
views
Proving that two languages both represent valid bracket sequences
I have two languages $L_1$ and $L_2$, both subsets of $\{0, 1\}^*$, defined as follows:
For $L_1$, we have that
$01 \in L$
If $w \in L$, then $0w1 \in L$
If $w_1, w_2 \in L$, then $w_1w_2 \in L$
For ...
2
votes
1
answer
101
views
$LL=\left \{ xyzy^R : xyz\in L \right \}$ is context free language
Let $L$ be a regular language over $\Sigma = \left \{ 0,1 \right \}$.
Define $LL=\left \{ xyzy^R : xyz\in L \right \}$ where $x,y,z\in \Sigma^*$. The question asked to show that $LL$ is context free ...
- 189
0
votes
1
answer
46
views
Confusion regarding the conversion of epsilon-NFAs to non-epsilon NFAs
I've begun reading up on NFAs and DFAs, NFAs of both the epsilon and non-epsilon kind
My understanding of epsilons are this: They help 'encode' the idea of taking another optional route without ...
- 103
3
votes
0
answers
116
views
Convert a regular expression to a *minimal* LL(1) regular grammar
Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1).
However, if we convert the ...
- 151
1
vote
1
answer
58
views
Give a class of languages which is closed under intersection and union, but not under complement
I am pondering this question, it is posed early on in a course on Formal languages and Automata, but before much progress has been made on closure of Regular and Context Free languages under ...
0
votes
1
answer
28
views
Proving Non-Semi-Decidability of Language L - Seeking Reduction Strategy
I'm working on a problem involving the language
𝐿 =
{
𝑤
∣
time𝑀𝑤
(
𝑥
)
≤
∣
𝑥
∣
+
1
for all words
𝑥
}.
The language consists of words
𝑤 where the Turing machine
𝑀𝑤 halts within
∣
𝑥
∣
+
1
...
- 1
3
votes
1
answer
196
views
Understanding a bound for derivation length of any string in Pumping lemma for context-free languages
The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz:
Let $L$ be an ...
- 137
3
votes
1
answer
49
views
Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?
There's been a question about an algorithm converting an arbitrary FSM into a backwards deterministic automaton without $\varepsilon$-transitions and a single initial state.
As commenters pointed out, ...
- 1,549
5
votes
1
answer
140
views
Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?
An automaton is backwards deterministic if, for all states q, p, for all symbols a:
$$
(\delta(q, a) = \delta(p, a)) \implies p = q
$$
(I think the right translation is backwards deterministic, but ...
- 53
2
votes
1
answer
43
views
FSA for 'closure' of a language; how to represent?
Is my interpretation of this correct?
I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA.
In order to do so, would I draw a new edge from the ...
- 87
1
vote
1
answer
26
views
Reachable States in a Product of Transition Systems
I am trying to deepen my understanding of transition systems and synchronization schemes and would appreciate some insights.
Consider the following scenario:
We have three transition systems A1, A2, ...
- 11
1
vote
1
answer
59
views
Splitting strings in pumping lemma for regular language
I was recently reading the book Introduction to the Theory of Computation, Second Edition by Michael Sipser, and encountered the following example:
Let $F=\{ww\ |\ w\in \{0, 1\}^*\}$. We show that $F$...
- 13
1
vote
0
answers
32
views
Effect of slight modification to LL(1) parse table generation
I am experimenting with LL(1) parsers that do not use a separate lexer.
I have the following grammar:
S = (('<' S '>' | 'a'+) ' '?)+
The notation uses ' ...
- 11
2
votes
2
answers
53
views
Is garbage state necessary in DFA that enforces a particular input combination?
If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
- 87
4
votes
1
answer
227
views
Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?
I am doing a HW problem where I have L1 and L2.
I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
- 87
7
votes
1
answer
328
views
Are Context-Free languages closed under XOR?
First, let's generalize the notion of XOR on strings over the ${0,1}$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $ \text{xor}(w, \...
- 73
0
votes
0
answers
21
views
Does a Moore Machine always require an output for start state?
My lecture notes show all moore machines as having an output even for q0, the starting state.
This video shows a Moore machine without an output for its starting state.
I understand that all Moore ...
- 87
1
vote
1
answer
84
views
How to formally prove that any regular expression can be written as a finite combination of base cases and operations?
In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows:
Based on this definition, how can I formally prove that any regular ...
- 113
1
vote
1
answer
50
views
Kleene star of any unary language is regular
I want to prove:
Let $L \subseteq \Sigma^*$.
If $\Sigma=\{a\}$, then $L^*$ is regular.
I found this answer:
Kleene star of an infinite unary language always yields a regular language.
But I do not ...
- 23
2
votes
1
answer
58
views
Counting words in an unambiguous context-free grammar
Given an unambigious context-free grammar $G = (\Sigma, V, \mathcal R, S)$, is there a polynomial-time algorithm that calculates $|L(G)|$ (including the case where $|L(G)|$ is infinite)?
The rough ...
- 21
0
votes
1
answer
67
views
Is the following language decidable?
Please confirm if my understanding of the below question, and my answer is correct.
Is the following language decidable? Justify your answer.
$L = \{\langle M_1,M_2\rangle \mid L(M_1) \cup L(M_2) = \...
- 103
0
votes
1
answer
37
views
0
votes
2
answers
52
views
Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma
I have a regular language $a(a+b)^*$ to which i applied pumping lemma.
Let the pumping length be $'p'$
and the example string be $$w=a(a+b)^{p-1}$$.
The string satisfies the condition that it is at ...
- 3
0
votes
0
answers
51
views
transforming a grammar from EBNF to LL(2)
I have a grammar in EBNF and want to transform it into an LL(2) grammar. Should I omit A -> empty string ? And is there a scheme I can follow? So far I would ...
3
votes
0
answers
49
views
Does this endomorphism over finite automata have a name?
I found this function that can be applied onto a DFA to produce a DFA. Is there a name for it?
Above: A simple DFA over the alphabet $\{0, 1\}$
Below: The resultant DFA over the alphabet $\{0\mathrm{$...
- 124
0
votes
0
answers
13
views
Critical Pair Determination in Knuth Bendix
In the Knuth Bendix completion algorithm, how does one identify all the critical pairs for an abstract term rewriting system? Does one have to iterate through each rule, and then identify which pairs ...
- 1
0
votes
1
answer
74
views
A specific class of languages
We say a languages $L$ is permutable such that $x\in L$ if and only if a permutation of $x$ be in $L$. Does the set of permutable languages is context-free or not?
I think there is a permutable ...
- 1,962
1
vote
1
answer
56
views
How to prove a function is a bijection (name mangling)?
I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed.
We'...
- 183
0
votes
0
answers
9
views
Does a Language Accepted by a Non-deterministic Turing Machine with Zero Errors Necessarily Belong to Class R
It is said that a non-deterministic Turing machine M accepts a language L with m errors if and only if:
For every x in language L, M does not accept x in at most m calculation routes.
for every x ...
7
votes
1
answer
137
views
Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?
Let $L$ be a language over an alphabet $\Sigma$ and let
$$ \text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \} $$
$$ \text{MAX}(L) = \{ w \in ...
- 213
0
votes
0
answers
23
views
Is complement of this language context-free? [duplicate]
Let $L = \{wcw : w \in \{a, b\}^\ast\} \subseteq \{a, b, c\}^\ast$. From what I know, this language is not a context-free language but how about complement of this language?
I know that the class of ...
- 61
-1
votes
1
answer
32
views
is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}
I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please?
$L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
- 203
1
vote
0
answers
41
views
Alphabet of Turing Machines and Diagonalization
When we are using a diagonalization argument, does it matter what the alphabet of the Turing machine we are using to do the diagonalization is? I think it does but I'm not 100% sure.
For example, ...
- 246
0
votes
0
answers
27
views
Why is it simpler to express the cut-elimination rule in general deductive systems than strictly formal systems?
This article says:
Depending on the strength of the metalanguage used to define the
judgments and steps, simply having a deductive system does not in
itself necessarily yield an effective procedure ...
- 140
0
votes
0
answers
33
views
How to use Jflex to generate a lexer properly?
I was told that making lexer from scrath is really hard and that we should use built in libraries. I used an already existing example to build my program. It worked but was full of error partially ...
- 11
0
votes
1
answer
130
views
Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"
I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively.
What I'...
- 13
2
votes
1
answer
86
views
Graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 61
1
vote
0
answers
57
views
A proof that $a^n b^m $ for $n\neq m$ is not regular by using the pumping lemma
I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular.
This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems.
...
- 485
1
vote
2
answers
99
views
Subset Relations Between CFGs and Their Languages
Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
- 15
0
votes
1
answer
124
views
Decidability of whether a Turing machine accepts all even-length words
In my quest to understand computability theory, I came across this question, and it made me think that I don't fully understand the theory.
Is this language decidable? Is it semi-decidable, co-semi-...
- 203
1
vote
0
answers
37
views
Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit
Background
I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
- 121
0
votes
0
answers
58
views
The formal proof that one Turing Machine computes one specific function
I have asked one similar question QA_1 "The formal proof that one Turing Machine recognizes one specific language" and the answer fills the part "It does not generate any string that is ...
- 203
0
votes
1
answer
70
views
The formal proof that one Turing Machine recognizes one specific language
When given one grammar, we can formally prove that it can recognize one language using QA_1
Since Kleene's Theorem gives the equivalence between the regular grammar and the NFA, we can also use QA_1 ...
- 203
0
votes
3
answers
67
views
Reference types
Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing?
I'm having a hard time wrapping my head around the concept fundamentally (of course, I have ...
- 183
0
votes
0
answers
39
views
How to determine class of formal language in Chomsky Hierachy
I recently started learning about the chomsky hierarchy and I am preparing myself for an upcoming exam. Often there are tasks to specify the smallest classification of a given formal language. How ...
2
votes
1
answer
45
views
Express a language containing the words with an odd amount of 0's using the languages $\{0\}$ and $\{1\}$
This is a homework question and after struggling with it for a while, I have decided to ask for help here.
The task is to construct a language over the alphabet $\{0,1\}$ consisting of precisely those ...
- 21