<we><edit> <!-- questions and answers -->
shortest-path
lambda-calculus
data-compression
cpu-cache
arithmetic
recurrence-relation
linear-algebra
programming-languages
concurrency
reductions
computational-geometry
asymptotics
nondeterminism
regular-languages
formal-grammars
neural-networks
trees
hash-tables
decision-problem
randomized-algorithms
image-processing
artificial-intelligence
heuristics
graphs
np-complete
formal-languages
Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free
formal-languages
context-free
pumping-lemma
Proving that $(A \cup B)^* = A^*(BA^*)^*$
formal-languages
automata
induction
If L is regular, is Pref[ Suff (L)] = L?
formal-languages
regular-languages
Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free
formal-languages
context-free
formal-grammars
Prove grammars with long derivations generate infinite languages
formal-languages
context-free
formal-grammars
How to show that a "reversed" regular language is regular
formal-languages
regular-languages
automata
finite-automata
A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"
formal-languages
turing-machines
computability
undecidability
Constructive Proof on Regular Languages
formal-languages
regular-languages
closure-properties
Is there a standard way to define a formal language transformer?
formal-languages
Proving P and NP on problems formulated as languages
complexity-theory
formal-languages
np
Kleene positive closure - help in proofing this claim
formal-languages
closure-properties
Formalism for unambiguous context-sensitive languages?
formal-languages
formal-grammars
parsers
Is there a way to find a simple regular expression for this language?
formal-languages
regular-languages
regular-expressions
context free grammar for "odd number of 1 and one 0" or "even number of 1"
formal-languages
regular-languages
context-free
Show that the collection of Turing-recognizable languages is closed under homomorphism
formal-languages
turing-machines
closure-properties
Closure of Turing-recognizable languages under homomorphism
formal-languages
computability
closure-properties
semi-decidability
Thompson Regular Expression Search Algorithm 3rd Stage
formal-languages
regular-expressions
search-algorithms
compilers
How to define a language for an independent set problem of a graph?
formal-languages
graphs
Can the regular image of a context-free language be undecidable?
formal-languages
regular-languages
context-free
closure-properties
Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages
formal-languages
context-free
reference-request
formal-grammars
Concatenation of two regular languages
formal-languages
regular-expressions
Turing machine that accepts L = {#a != #b}
formal-languages
turing-machines
automata
Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5
formal-languages
finite-automata
nondeterminism
Conversion of ambiguous left recursive grammar to LL(1)
formal-languages
formal-grammars
parsers
left-recursion
Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)
formal-languages
regular-languages
automata
finite-automata
A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers
formal-languages
automata
finite-automata
Can someone give a generic definition of any Definite Language in set builder notation?
formal-languages
regular-languages
automata
finite-automata
Closure of context-free languages under "removal of a regular language from the right"
formal-languages
context-free
What are definite languages? How do you formally define them?
formal-languages
regular-languages
automata
finite-automata
CFG - Left factoring in recursive nested productions
formal-languages
context-free
formal-grammars
compilers
parsers
How to reduce language is finite to language is regular?
formal-languages
reductions
decision-problem
Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?
algorithms
formal-languages
regular-languages
finite-automata
regular-expressions
Is unary language with polynomial power context sensitive?
formal-languages
context-sensitive
PDA for concatenated languages
formal-languages
automata
pushdown-automata
Pushdown automata for $\{a^m b^n c^{mn} | m,n\geq1\}$
formal-languages
pushdown-automata
Wrong DFA from NFA. String Does not contains 110
formal-languages
finite-automata
Meaning of # in descriptions of languages
formal-languages
regular-languages
pumping-lemma
Use the pumping lemma to prove that {www} is not context-free
formal-languages
context-free
pumping-lemma
Designing a Grammar for $L(G) = \{α ∈ T^* \ | \ |α|\ ≡\ 5\ mod\ 7 \}$
formal-languages
finite-automata
formal-grammars
How to prove that a transformed language is regular using an NFA
formal-languages
regular-languages
finite-automata
closure-properties
Can three regular languages be concatenated?
formal-languages
regular-languages
regular-expressions
Designing a DFA that accepts strings such that nth character from last satisfies condition
formal-languages
regular-languages
finite-automata
Closure properties of linear context-free languages
formal-languages
context-free
formal-grammars
closure-properties
How to prove a language is regular?
formal-languages
regular-languages
automata
proof-techniques
reference-question
Closure under swap operator
formal-languages
regular-languages
closure-properties
Using Myhill-Nerode to prove a language is non-regular
formal-languages
regular-languages
Regular Expression Building
formal-languages
regular-languages
regular-expressions
Basic doubt in converting PDA to DPDA
formal-languages
context-free
pushdown-automata
Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
formal-languages
context-free
formal-grammars
Grammar/Chomsky-Type for $L = \{ww \mid w \in \{a,b\}^*\}$
formal-languages
formal-grammars
chomsky-hierarchy
Shortest Path using at most k colors
formal-languages
graph-theory
shortest-path
routing
Evaluation semantics: reduction rule for a split statement
formal-languages
semantics
term-rewriting
Unambiguous grammar for regular expressions
formal-languages
context-free
regular-expressions
Does this proof work for infinite regular languages
formal-languages
regular-languages
closure-properties
Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?
formal-languages
logic
lambda-calculus
curry-howard
computational-linguistics
Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode
formal-languages
regular-languages
What parts of a programming language can't be defined using Regular Expressions?
formal-languages
context-free
regular-expressions
Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular
formal-languages
regular-languages
pumping-lemma
It is possible to write any program (i.e. Turing complete) with just one single expression?
formal-languages
turing-machines
automata
lambda-calculus
church-turing-thesis
Choose a specific regular language to prove a language is not regular
formal-languages
regular-languages
closure-properties
Set of infinite DFA's
formal-languages
turing-machines
regular-languages
Turing machine halting in at least 100 steps on all inputs
formal-languages
turing-machines
Does every undecidable problem contain a decidable subset?
formal-languages
undecidability
Are regular languages closed under inverse homomorphism?
formal-languages
regular-languages
closure-properties
Confused b/w non-deterministic finite state automata vs finite state automata
formal-languages
finite-automata
nondeterminism
Can a DPDA decide if two letters appear the same number of times mod 5?
formal-languages
context-free
pushdown-automata
Does the language of TM's that repeat a configuration infinite times semi-decidable or not?
formal-languages
computability
reductions
undecidability
semi-decidability
Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $
formal-languages
Is an inverse homomorphism always a homomorphism?
formal-languages
Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms
formal-languages
regular-languages
Not able to prove non regularity using pumping lemma
formal-languages
regular-languages
pumping-lemma
Decidability of intersection of two languages of same type
formal-languages
computability
automata
undecidability
semi-decidability
How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?
formal-languages
regular-languages
context-free
formal-grammars
Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?
formal-languages
context-free
pumping-lemma
pushdown-automata
Which language is produced by this grammar?
formal-languages
formal-grammars
Recursive definition of a language $ L $ over $ \{a,b\} $
complexity-theory
formal-languages
regular-languages
recursion
Is square numbers written in binary a regular language?
formal-languages
regular-languages
automata
finite-automata
turing machine for the language L ={w#w' where w<w'}
formal-languages
turing-machines
Why does a Turing Machine need at least two states?
formal-languages
turing-machines
P reduction between np-complete to np-complete
complexity-theory
formal-languages
turing-machines
reductions
Grammer Class/Production Rules of Programming Languages
formal-languages
formal-grammars
programming-languages
Explaining why a grammar is not LL(1)
formal-languages
regular-languages
context-free
pushdown-automata
Is the language given by a context-free grammar always context-free?
formal-languages
context-free
formal-grammars
Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$
formal-languages
formal-grammars
context-sensitive
Is there an analog of "regular" for infinite strings?
formal-languages
regular-languages
Is there any difference between these two languages?
formal-languages
regular-languages
finite-automata
DFA accepting strings with at least three occurrences of three consecutive 1's
formal-languages
finite-automata
formal-grammars
compilers
Show that this language is not regular by Pumping Lemma
formal-languages
regular-languages
pumping-lemma
Is the complement of every non Turing recognizable language a Turing recognizable language?
formal-languages
formal-grammars
Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$?
formal-languages
What is the difference between language hierarchy and Grammar hierarchy for LL and LR?
formal-languages
formal-grammars
Reduction from L to Htm
complexity-theory
formal-languages
turing-machines
reductions
How to compare the efficiency of two encoding schemes or hypothesis languages?
formal-languages
terminology
efficiency
coding-theory
encoding-scheme
Finding language family of given language
formal-languages
regular-languages
automata
finite-automata
pushdown-automata
What are applications of the levels of the Chomsky hierarchy?
formal-languages
turing-machines
Reduction function from A to its complement
complexity-theory
formal-languages
turing-machines
reductions
Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?
formal-languages
turing-machines
computability
automata
Systematic approach or algorithm for designing a pushdown automata that accepts a langauge
algorithms
formal-languages
pushdown-automata
Intersection of languages using closure properties
formal-languages
regular-languages
Is the set of TMs whose language reduces to a fixed CFL also CFL?
formal-languages
turing-machines