All Questions
17
questions
0
votes
1
answer
87
views
What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?
Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
3
votes
1
answer
50
views
Finding a bound for existential quantification
Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set.
$$
L = \left\{ (x, \alpha, \beta) \in \omega \...
- 3,468
3
votes
1
answer
84
views
Why is reflexivity a feature of multi-step β-reduction, and not of β-reduction?
I understand the need to distinguish between two algorithms, even when one is enclosed in another. Transitivity as a feature of multi-step reduction makes perfect sense, since we literally need ...
- 692
2
votes
1
answer
187
views
Parenthesization in Lambda Calculus
I am trying to understand how parenthesization works in $λ$-calculus. All of the resources state the following:
Applications are left associative;
Abstractions are right associative and extend as ...
- 339
1
vote
1
answer
446
views
Backus Normal Form and Logic
Given the alphabet of ${P, P_1, ..., Q, Q_1, ..., R, R_1, ..., ..., ¬, ∧, ∨, →, (, ) }$, write a Backus normal form grammar that generates all legal propositional formulas. For the start it is given ...
- 312
0
votes
1
answer
52
views
Inverse image of the image of a formal language and vice versa
I'm not sure if I've understood inverse images correctly, so I want to ask if my following thoughts are correct:
Suppose, $\Sigma =\{a,b\}$, $L$ and $R$ languages over $\Sigma$ and $h:\Sigma^*\to \...
- 1,197
1
vote
1
answer
43
views
Prove, that the following rules for homomorphisms are true or false.
Let $\Sigma=\{a,b\}$, $L$ and $R$ be languages over $\Sigma$ and $h:\Sigma^* \to \Sigma^*$ be a homomorphism. Prove or disprove the following statements:
$h^{-1}(L\cup R)=h^{-1}(L)\cup h^{-1}(...
- 1,197
2
votes
1
answer
69
views
finding grammar for languages
Situation: So I have three languages.
a) $L_1 =$ { $a^{2n-1}b^{2m} | n,m \geq 1$}
b) $L_2 =$ { $a^nb^ma^nb^m | n,m \geq 1$}
c) $L_3=$ { $a^nb^ma^{n+m} | n \geq 1, m \geq 0$}
So one of this ...
- 1,143
2
votes
5
answers
2k
views
Are context free languages closed under taking substring?
Let $L$ be context free and $\Sigma $ an alphabet
Define $s(L):=\{y \in \Sigma ^*\mid \exists x,z \in \Sigma ^*: xyz \in L\}$
Is $s(L)$ context free ?
I haven't been able to find a counterexample ...
- 1,753
1
vote
1
answer
255
views
What type of grammar is this?
I'm working on this problem:
Suppose a phrase-structure grammar has productions: $ S\to 1S0, S\to0A, A\to 0 $. What type of grammar is this, why?
Would this be considered a type 1 grammar? I'm ...
- 35
4
votes
1
answer
2k
views
Identify inherently ambiguous languages
Which of the following languages is/are inherently ambiguous languages?
$L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$
$L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$
My attempt:
A ...
- 4,785
1
vote
0
answers
46
views
Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines
The question is:
Let $A$={11,00}.
Find $A^n$ for n=0,1, and 3.
Would i be right in thinking that
$A^0$ = {λ}
$A^1$ = {11,00}
$A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}.
if ...
- 11
0
votes
1
answer
32
views
Length of substring if we just consider a subdivision in $\log n$ substrings
Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
- 18.2k
2
votes
2
answers
1k
views
Finding a grammar for given language
So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be.
The language in this problem is: $\{bb, bab, baab, baaab,.....
- 101
2
votes
0
answers
882
views
Recursive definition of a language
Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria:
All words in L contain the substring aa an odd number of times.
All words in L are such ...
- 21