0
votes
0answers
20 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
1
vote
2answers
159 views

$\beta$ - conversion and $\alpha$-reduction problem in $\lambda$-calculus

Here is an expression that I am trying to reduce and my operations so far: $$((\lambda x.(x (\lambda z.zy))) (\lambda z.\lambda y. zy) )= (x (\lambda z.zy))[x \to \lambda z.\lambda y. zy ] = ...
0
votes
1answer
56 views

Is this $\beta$-reduction well defined?

Would it be possible to apply $(\lambda x.\lambda y. x)$ to the argument $y$? It seems to me that this must not be possible as it would give a different answer if applied to a constant, call it ...
1
vote
1answer
69 views

Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say: < is a strict partial order and R is an irreflexive and ...
1
vote
1answer
103 views

Understanding recursion in λ calculus

In recursion for λ calculus, I was wondering why the following two are equal (λx.g (x x)) (λx.g (x x)) g ((λx.g (x x)) (λx.g (x x))) How shall I understand g ((λx.g (x x)) (λx.g (x x)))? ...
0
votes
1answer
202 views

The way that a regular expression describes a regular language

A formal language is a set of words in some alphabet. It may be defined as being generated by a formal grammar or as being recognized by an automaton. For a regular language, it can also be described ...
2
votes
2answers
369 views

Can a formal language always be generated by a formal grammar?

A formal language is often defined by means of a formal grammar. I wonder for a formal language if there is always a formal grammar that generates the language? Does this answer have something to do ...
0
votes
3answers
188 views

Is a regular expression a string or a set of strings?

Quoted from Introduction to the Theory of Computation by Sipser, a regular expression is defined as: Say that R is a regular expression if R is a for some a in the alphabet $\Sigma$, ...
0
votes
2answers
147 views

Formal language problem

I’m new to formal language and searching for the solution for the following task: $\Sigma$ is an alphabet with $\lvert \Sigma\rvert = 5$ and $k \in \mathbb{N}_0$. I’m searching for $\lvert ...
0
votes
3answers
188 views

Formal language problem

Hello I´m new to formal language and searching the solution for the following task: Language: $L = \{0^{2i+1}|i\in\mathbb{N}_0\}$ Alphabet: $\Sigma = \{0\}$ I'm searching the resultion (sic) for: ...
2
votes
2answers
309 views

Recognizing language using Turing machine

Given integers $a, b, c$ construct a single-tape Turing machine recognizing the language $\{w \in \{0,1\}^{*}: a*\#_{0}w+b*\#_{1}w+c=0\}$ in time $O(n*logn)$, where $n=|w|$. $\#_{x}w$ denotes the ...
2
votes
1answer
241 views

Detecting cycles in off-line Turing machines

Let $M$ be an off-line Turing machine over the input alphabet $\{0,1\}^{*}$, that uses only one working tape in addition to the input tape. Construct a Turing machine $M'$, such that: $L(M) = ...
9
votes
1answer
344 views

is this language context free? [closed]

I need an NPDA for the following language if it is context-free, and if it isn't I need a proof using the pumping lemma that it is not a CFL: $$L_1=\{w_1w_2 \in \{a,b\}^* : |w_1| = |w_2|,w_1\neq ...
4
votes
1answer
151 views

Help understand $\text{handle}$ in parsing problem

The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the ...
2
votes
1answer
128 views

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet {0,1}?

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language {$w \pi_1(w) \pi_2(w)$} over alphabet {0,1}? Polynomial size in $|w|=n$
3
votes
3answers
257 views

Software/algorithm for the smallest context free grammar describing a set of words?

I am looking for software/algorithm for the smallest context free grammar describing a finite set of words (and no other words). For a single word I found sequitur Related to this seems: given a CFG ...
4
votes
2answers
3k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
3
votes
1answer
209 views

Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears 0 or 2 times Word repetition {www* | w \in \Sigma *} (word repetition of an arbitrary word w) ...
2
votes
1answer
250 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
5
votes
5answers
688 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...