Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,296
questions
1
vote
0answers
24 views
Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
2
votes
1answer
649 views
Is it true that if L* is recursive, L is also recursive?
Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?
I know that the opposite direction is true:
If $L$ is recursive, then $L^*$ is recursive.
But I don't know how ...
0
votes
0answers
36 views
Turning grammar to LL(1)
I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1).
...
-4
votes
0answers
30 views
Show that for any language L, L* = (L*)* = (L+)* = (L*)+
Please answer this question it means a lot for me.
3
votes
0answers
41 views
Are there context free grammars for all restricted Dyck paths?
A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...
-1
votes
1answer
17 views
Formal definition of non deterministic PDA
How would you convert the following formal definition of deterministic pushdown automata into non deterministic ?
Deterministic PDAs In general terms, a deterministic PDA is one in
which there is at ...
2
votes
2answers
50 views
Prove that every regular subset of $a^nb^n$ is finite
How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $...
1
vote
1answer
18 views
When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?
A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current ...
2
votes
0answers
26 views
Regular string relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := ...
4
votes
1answer
222 views
What is the computational complexity of “real-life” regular expressions?
Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), ...
0
votes
0answers
54 views
What does it take to create a new programming language and its toolchain?
I am super novice to this topic, so my apologies if my question looks completely nonsense to you all!
Imagine you want to create a new programing language that transpiles to a more common high/low-...
1
vote
1answer
357 views
What are the modern alternatives to Backus–Naur form and what are their advantages?
I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
1
vote
1answer
32 views
Number of equivalence classes
Given language $L$, why is it not necessarily true that the number of equivalence classes of $L$ is equal to the number of equivalence classes of $L^R$?
And for the private case that $L$ is regular, ...
-1
votes
1answer
26 views
Turing Machine construction of M=wwRw form
Construct a Turing machine for
M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}.
I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
2
votes
1answer
29 views
Language of lists of words, not all of which are different, is not context-free
How do I prove that the following language isn't context-free using the pumping lemma?
$$
L=\{w_1\#w_2\#\dots\#w_k \colon k ≥ 2, w_i \in \{0,1\}^*, w_i = w_j \text{ for some } i \ne j\}
$$
I am having ...
-1
votes
1answer
38 views
Create a PDA for the given language
The task is to create a PDA for this language. The |u| a reffers to the number of a's in that word. I have tried working on it as two separate languages that I can later combine, but I fail to even do ...
14
votes
1answer
423 views
Is the language of words that are unbalanced in the first half context-free?
(Practice exam question in computational models)
Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.
Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
0
votes
1answer
32 views
Show that a decidable language is not decided by a decider in a given set
M.Sipser's Introduction to the Theory of Computation offers the following problem in its chapter on decidability:
Let A be a Turing-recognizable language consisting of descriptions of Turing machines,...
1
vote
1answer
42 views
necessary and sufficient pumping lemma - bounded pumping variant
There exists a variation of the pumping lemma with necessary and sufficient conditions for a language to be Regular.
According to that lemma:
A language $L$ is regular iff $\exists k$, $\forall x\in ...
0
votes
1answer
31 views
Complement of $0^n1^n | n \in \mathbb{N}$
I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \{ 0^n 1^n | n \in \mathbb{N}\}$ is $A = \{ 0^i 1^j| i \neq j\} \cup (0 \cup1)^*(1)(0 \cup1)^*0(0 ...
-2
votes
2answers
78 views
Is a 'discrete language' well-defined?
Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ?
An argument w is a member of L under the following rules...
Example1:
If more than half of w's digits are 1's --...
0
votes
0answers
27 views
Is language bin(n)bin(2^(k+1) n + 1)^R context-free
I have a problem with this exercise. For language $$L_1 = \{ w \in \{0, 1\}^* : \exists k \in \mathbb N \ w = \text{bin}(n)(\text{bin}(2^{k+1}n + 1))^R \},$$ where $\cdot^R$ reverses a string and $\...
1
vote
2answers
92 views
Do there exist coding languages where the halting problem is solvable but not trivial
Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages ...
0
votes
2answers
25 views
Is the language of rectangular matrices in MATLAB-style syntax context free?
Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ...
1
vote
3answers
33 views
Why is casting float to double applicable?
This is indeed a Computer Science Question.
As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits.
e.g
<...
0
votes
0answers
55 views
context-free language : if yx belongs to cfl then xy is also cfl [duplicate]
I faced a problem.
What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language.
C is a Context-Free Language.
I think we can use the PDA ...
0
votes
1answer
32 views
Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }
I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.
This is really confusing me, I'm having trouble with ...
1
vote
1answer
34 views
Designing CFG that accepts $b^m a^n$ ($m ≤ n$)
I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?
0
votes
1answer
36 views
Is the empty string and some words of even length are elements of this set?
$L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.
I have my answers, but I need confirmation:
Is the empty string $\epsilon \in L$? Yes. Reason: ...
2
votes
1answer
54 views
When our two-state PDA constructed from CFG is non-deterministic PDA?
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
-1
votes
1answer
23 views
Shortest unambiguous representation of a graph over an alphabet
I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:
Given the graph with the matrix ...
2
votes
1answer
50 views
Difference between assignment, binding, and substitution?
I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration,...
-1
votes
1answer
29 views
How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Let us consider the following Context-Free Grammar
G = ({S,A,B,C,D},{a, b}, S, P)
with production rules P:
S → SSA | Bb
A → BSA
B → A | Cb
C → AD | Cb | ɛ
D → a | b | ɛ
Let L be the language ...
0
votes
2answers
22 views
PDA with more than one initial state
I'm wondering if PDAs with more than one initial states are also accepting context free languages.
If found that question on this site about NFAs and would like to know if this answer is also valid ...
-1
votes
1answer
31 views
Proof for palindrome grammar by induction
I can't seem to find a solution to the following question.
Given the following grammar for palindromes:
$$G_{pal}=\{\{a,\dots,z\},\{P\},P,R\},$$ with $R$ consisting of the rules
...
1
vote
2answers
149 views
Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?
I was given a question and don't really know to solve it.
Given a regular language $L$, is the following language also regular?
$$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length ...
0
votes
0answers
35 views
Converting CFG to GNF problem
I have a big problem with converting GNF example.
This is my CFG
$
S \to AS\mid BS\mid \lambda\\
A \to aC\mid BCA\mid c\\
B \to AB\mid b\mid \lambda\\
C \to S\mid d
$
I simplified the CFG by ...
1
vote
1answer
96 views
Check if language is decidable
I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.
I know that every finite ...
2
votes
1answer
26 views
Decide if a language has a word of a given size
Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:
$$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ ...
0
votes
0answers
10 views
Are DPDAs accepting on final state equivalent to DPDAs accepting on empty stack equivalent? [duplicate]
Say I have a string x that is accepted by some DPDA P that accepts empty stack. Intuitively it's seems impossible for P to accept any string x.y for any y != epsilon. The below DPDA accepts on final ...
1
vote
1answer
22 views
Formal defintion of SET-PARTITION as a language
I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it
$$
\left\{ \langle S,A,B\rangle \;\middle|\; (A,B) \text{ is partition of } S \text{ and } \sum_{n\in A} n = \sum_{n\...
1
vote
1answer
41 views
Languages A, B ∈ NP-complete such that A⋃B = Σ*
I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a ...
0
votes
2answers
57 views
Are all language over $\Sigma= \{0\}$ decidable?
I have problem in determine whether it is decidable or not, can somebody help me please
0
votes
1answer
24 views
Is that true that A is decidable if A$\le_m$A complement? [duplicate]
A is decidable if A$\le_m$A complement
Can i think that it is true because decidable is close under complement, so if A complement is decidable, so is A
-2
votes
1answer
27 views
Grammar with a long derivation generates an infinite language
Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$
generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite.
This question is ...
1
vote
1answer
30 views
CFG for a given languague
Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$.
I am currently trying to solve the given task, I thought a good way is to split ...
0
votes
1answer
53 views
Is there possible that undecidable language A, where A is mapping reducible to A complement?
Is there possible that undecidable language A, where A is mapping reducible to A complement?
If it is possible, since A is undecidable language, so must A complement too is also undecidable language, ...
1
vote
1answer
73 views
How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?
I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and ...
0
votes
1answer
46 views
Same notation/terminology for union of sets and concatenation (Kleene star)?
For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
-2
votes
1answer
21 views
Minimization of automata with dead state
I am supposed to minimize the following DFA automa, which contains dead state:
But after the minimization of the automata, it stayed the same.
Is it correct?
