All Questions
Tagged with context-free automata-theory
34 questions
0
votes
0
answers
39
views
Are there approaches to deriving a Grammar(production rules) from given set of strings?
Apologies for unambiguous question. So far I have a lot of difficulties of discerning on how to design formal production rules for some formal language aside from classic examples such as equal pairs ...
- 9
6
votes
0
answers
112
views
Extensions of linear integer arithmetic decidable via Deterministic Pushdown Automata
I've recently learned about the connection between linear integer arithmetic (Presburger arithmetic) and Deterministic Finite Automata (DFAs). Namely, any formula in the first order theory of ...
- 161
5
votes
2
answers
159
views
Modify DCFG to enforce length limit
Given a deterministic context-free grammar $G$ that generates the language $L$, is there an efficient algorithm that can be used to construct another DCFG $G_N$ that generates the language $\{ s \in L ...
- 163
4
votes
1
answer
215
views
Pumping lemma for CFL intersection
The class of context-free languages is not closed under intersection. For example, the language $L=\{a^nb^nc^n : n\geq 0\}$ is not context-free, but it is an intersection of two context-free languages....
- 303
5
votes
0
answers
88
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 581
1
vote
1
answer
157
views
Bounded non-emptiness intersection of deterministic context-free grammars
Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
- 11
9
votes
0
answers
113
views
Expressiveness of pushdown automata whose stack height sequence is unambiguous
I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...
- 9,838
2
votes
1
answer
162
views
Does a finite, polynomially-bounded CFG translate into a polynomially-bounded DFA?
We are given a family of context-free grammars $\{ G_1, G_2, G_3, ..., G_n, ...\}$ where each $G_n$ generates strings only of length $n$ and obeys other constraints specified below. We want to study ...
- 444
2
votes
0
answers
109
views
Necessary and sufficient condition for an infinite tree to be context-free
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
- 203
7
votes
0
answers
117
views
Deciding whether DCFG is visibly pushdown
Is the following problem decidable?
If so, what's the best algorithm known?
Instance: a deterministic pushdown automaton $A$
Question: Does there exist (i) some partition of the alphabet into push, ...
- 917
3
votes
0
answers
164
views
Deciding whether an arbitrary context-free grammar generates a deterministic push-down automata?
I know that it's undecidable whether an arbitrary context-free grammar is ambiguous, but is it decidable whether that grammar is deterministic? I can't find the answer to this question anywhere on the ...
- 131
11
votes
3
answers
1k
views
Maximum shortest word accepted by pushdown automata
Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
- 917
6
votes
1
answer
757
views
Are endmarkers necessary for Deterministic Pushdown Automata?
In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
- 103
5
votes
1
answer
218
views
Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?
It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most ...
- 14.2k
9
votes
3
answers
569
views
Continuous mathematics and formal language theory
Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.
For example, solving the intersection non-emptiness problem for a context-free ...
- 91
9
votes
1
answer
903
views
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
$\mathrm{CFL}$ is the class of context-free languages.
Question
Is $\mathrm{CFL}$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $\mathrm{DCFL}$?
- 5,167
2
votes
1
answer
231
views
Deformation of finite regular languages [closed]
Let $L \subseteq \{0,1\}^n$ be any finite regular language s.t it has an acyclic DFA.
Let $C$ be some class of acyclic DFAs.
Let $\sigma \in S_n$ be a permutation on $n$ symbols. We can apply $\...
- 31
17
votes
2
answers
330
views
A reference for a "more algebraic" approach to pushdown automata and CFLs?
In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly ...
- 464
17
votes
1
answer
2k
views
Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?
In the formal description of Deterministic Pushdown Automata, they allow $\epsilon$ moves, where the machine can pop or push symbols onto the stack without reading a symbol from the input. If these $\...
- 1,152
10
votes
1
answer
352
views
What is the state complexity of the copy language?
Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.
In words, $L_n$ is the set of copy strings of length $2n$.
Consider the following ...
- 5,167
4
votes
1
answer
280
views
What characterizations exist for the grammars that can express subsets of the context-free languages?
It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$.
...
- 2,962
6
votes
2
answers
195
views
Are deterministic context-free languages closed under outfix (or other erasing operations)
Define the outfix of a language $L$ to be
$Outf(L) = \{xy \mid \exists z. xzy \in L \}$.
Are any known results about whether deterministic context-free languages are closed under this operation, or ...
- 2,962
1
vote
0
answers
92
views
Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?
Which paper first showed that any context-free grammar (CFG) is equivalent to some CFG in Chomsky normal form?
I cannot find an reference.
- 113
0
votes
1
answer
386
views
is determining an unknown CFL from intersection of two CFLs decidable?
this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ...
- 11.1k
-2
votes
1
answer
724
views
Intersection between context-free and context-sensitive language decidability [closed]
I'm trying to find a formal proof of the following fact:
Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($...
- 1
16
votes
1
answer
567
views
Are there variants of visibly pushdown automata that allow pushing of words onto the stack?
I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack.
Alternately, a construction which ...
- 2,962
4
votes
1
answer
960
views
Minimal context-free grammar for a regular language
Are there any algorithms for solving exactly the following question?
Given a regular language L, represented as a finite automaton say, what is a CFG with minimal number of nonterminals that generates ...
6
votes
0
answers
286
views
Language of stack configurations of a pushdown automaton
Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?...
- 9,838
-1
votes
1
answer
88
views
Issue in understanding conditional likelihood for a producton rule
The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
- 103
32
votes
1
answer
941
views
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
- 771
9
votes
2
answers
9k
views
Why is non-determinism (Push-down automata) necessary?
I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such ...
- 201
10
votes
1
answer
810
views
Closure of unambiguous context-free languages under pre- and postfix.
Let $L$ be a context-free language. Define $ppc(L)$ to be the pre- and postfix closure of $L$, in other words, $ppc(L)$ contains all of $L$'s prefixes and postfixes, and hence $L$ itself. My question: ...
- 11.6k
5
votes
1
answer
1k
views
The class CFL\cap co-CFL
Is anything nontrivial known about the class $\mathrm{CFL}\cap \mathrm{coCFL}$? In particular, is it known whether $\mathrm{CFL}\cap \mathrm{coCFL} = \mathrm{DCFL}$ (certainly the reverse containment ...
- 732