Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,226
questions
0
votes
0answers
6 views
FOIL system for learning PROLOG rules from facts
I'm trying to use FOIL, a system from the 1990s developed by Ross Quinlan, to learn Prolog rules from facts. However, the input file syntax is tricky for me. Could someone provide me an example input ...
1
vote
2answers
9 views
Two regular languages over the same alphabet, regular or not regular?
TRUE or FALSE:
Let $L_1, L_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\{w\in\Sigma^* \mid w\in L_1 \text{ or } w\notin L_2\}$ is regular.
So we have to ...
0
votes
0answers
10 views
Proving a language is context free without closure rules or grammar?
I know how to prove a language is context free through closure rules and through providing a grammar. However, in my exercises I've come across a language not suitable for either:
$L = \{uc^nv\ \ |\ \...
1
vote
1answer
16 views
Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?
I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.
However, I've encountered this statement from my notes:
With $\epsilon$ productions in the ...
1
vote
1answer
26 views
Proving that a language satisfies the pumping lemma condition
I have to proof that $L = \{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \}$ is a regular language, and how it meets the Pumping Lemma condition.
For the PL, there is a string $xyz \in L$ such that $y \neq ...
0
votes
0answers
13 views
Cut word from regular language into two parts and swap them. Is the language still regular? [duplicate]
Define language $L’$ for given regular language $L$ as: $$L’=\{uv | u,v\in\Sigma^{*}, vu\in L\}$$ is language $L’$ also regular?
Hello, I need some help with solving this question.
I need somehow to ...
0
votes
2answers
31 views
How to prove this language is context free?
There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.
$L = \{a^{(n+1)} b^{(...
1
vote
1answer
14 views
Unambiguous grammars with different right and left hand derevations
I read recently that for an unambiguous grammar the left hand derevation need not necessarily be equal to the right hand derevation. Can someone give an example of this.
0
votes
0answers
26 views
Is there a pda with maximum 3 state for every CFL?
This is the first question I'm asking here
I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
2
votes
1answer
124 views
What is the relation between parsing languages and checking languages?
I have looked at a number of textbooks on computability theory. They typically have the following form:
Define a language class (regular, context-free, context-sensitive, recursively enumerable)
...
0
votes
0answers
15 views
How can I create the context free grammar for this language? [duplicate]
I need help finding the context-free grammar for this language.
$$ L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{$i,j,k \geq 1$, and $i=j$ or $i=k$ or both}\}. $$
I've found a way to satisfy $i = j$ ...
0
votes
0answers
22 views
how to write a language for context-free grammar generates the empty string?
How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
1
vote
1answer
29 views
How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?
This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.
$$ \text {Let }b_i \text{ denote } i \text{...
2
votes
1answer
57 views
Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$
The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$.
We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*...
-1
votes
1answer
32 views
Can an infinite regular language be decomposed in this way?
If $A$ is an infinite regular language, can there exist a finite regular language $B$ such that $A = BB^*$?
4
votes
2answers
830 views
If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?
If $L$ is not regular and $ L \subset L_1$, does it follow that $L_1$ is not regular also? Can you please provide an explanation? Thanks in advance.
0
votes
0answers
41 views
Prove that regular languages are closed under Kleene star [duplicate]
Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too?
I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
-1
votes
1answer
24 views
What is the language generated by this grammar?
I'm struggling to find the language generated by the following grammar:
Any help would be appreciated.
0
votes
0answers
11 views
How to write regular expression [duplicate]
The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's
Can you guys tell me what is the correct answer for this ?
0
votes
1answer
50 views
Are there more languages than functions?
My gut says "no", but I don't know why.
For any function $f$ over strings on an alphabet, one can define a language in which every word is just the concatenation of a string $s$, a delimiter, and $f(...
1
vote
1answer
32 views
Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable
I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable.
I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ ...
1
vote
2answers
59 views
Prove the following language is regular?
Assume $L_1$ is a regular language, and define:
$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$
Show that $L$ is regular.
I first tried to prove by showing ...
0
votes
1answer
19 views
EVEN-CFL Decidable / Undecidable - Rice-Theorem
Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$
Question : Is EVEN-CFL ...
4
votes
0answers
53 views
Reference on relating Post systems to string rewriting systems and formal grammars?
wikipedia states:
Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]
It has been proved that any Post canonical system is reducible to such a ...
0
votes
2answers
43 views
Formal grammar with constraints on the number of each symbol
I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in ...
0
votes
1answer
24 views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
0answers
36 views
NFA-$\epsilon$ extended transition function for inverted strings
It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows:
\begin{align*}
\hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\
\hat\delta(q,\epsilon) ...
1
vote
3answers
127 views
Large DFA to regex?
For an assignment for one of my courses, one of the questions is to provide a regular expression for the language:
"the set of strings such that the number of 0’s is divisible by six, and the number ...
0
votes
0answers
15 views
Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]
So.. my professor mentioned that it has something to do with
$Wi = a^5b^i$
$Zij = c^(i+5)$
which is in the language
But then mentioned that
$Wj = a^5b^j$
$Zij = c^(i+5)$
Is not in the language, ...
1
vote
1answer
32 views
Do closure properties for languages go the other way?
For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?
0
votes
1answer
33 views
Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e
An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\...
0
votes
0answers
28 views
One-way-function based on Friedberg numberings
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
2
votes
1answer
106 views
Prove {<M> | TM M on input 3 at some point writes symbol “3” on the third cell of its tape} is recursively enumerable but not recursive
Question: Let $$S =
\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape}
\}.$$ Show
that $S$ is r.e. (Turing acceptable) but not recursive ...
0
votes
0answers
31 views
Handling left recursion without left factoring with stateful parser combinators
Consider the language of simple types
$$
T \mapsto B \ \mid\ T \rightarrow T \\
B \mapsto \text{Bool} \ \mid\ \text{Int}
$$
where $\mapsto$ stands for productions to avoid ambiguity with the ...
0
votes
1answer
28 views
How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.
Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
4
votes
1answer
87 views
Prove or disprove {wtw^R | |w| = |t|} is context free
The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$
It looks like the language can be "pumped" by context free pumping lemma, ...
0
votes
1answer
38 views
CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$
Given the language:
$$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$
I propose the following grammar:
$$ \begin{align*}
S &\to \varepsilon \mid aSbS \mid bSaS \\
S &\to ...
1
vote
2answers
251 views
There exists an algorithm to find grammar of complement of a function?
I'm wondering if there exists an algorithm to solve the following problem:
Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar
$S'$ such as $L(S) = L(S')^c $.
I note ...
1
vote
1answer
72 views
Using MyHill Nerode theorem to prove a language is non-regular
The language is $S = (a^nb^m | n \geq m)$.
I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that ...
1
vote
1answer
36 views
Proving the regularity of the following language
I have a question about the following problem:
Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over
$\Sigma = \{a,b\}.$
I know that in proving a language is regular I ...
1
vote
2answers
80 views
Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
-1
votes
1answer
38 views
Set-theoretic difference of two languages in CFL - REG
Let $L_1,L_2\in$ CFL $-$ REG, with $L_1\subset L_2$. Which of the following always holds?
$L_1-L_2\in$ CFL $-$ REG and $L_1-L_2\in$ REG.
$L_1-L_2\in$ REG and $L_2-L_1\in$ CFL $-$ REG.
$L_1-L_2\in$ ...
1
vote
1answer
45 views
Use the pumping lemma to show it's not regular
I just learned pumping lemma this week and got confused on this question.
B={$a^{fn}$ | $f_n$ is a Fibonacci number} for $a \in Σ$.
Hint: the sequence of Fibonacci numbers get increasingly further ...
0
votes
1answer
23 views
Equivalent regular grammar with minimum number of nonterminals
Given a set of terminal symbols $\Sigma=\{a,b\}$ and a set of nonterminal symbols $N=\{S,A,B\}$ with start symbol $S$, then the two following sets of production rules are equivalent:
$S\to aA$
$A\to ...
3
votes
2answers
165 views
If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?
I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack.
But, a link of Show that { ...
-1
votes
1answer
58 views
Is a language regular if a word is in a regular language but the reverse is not?
$$A_1 = \{ x \mid x \in A , x^R \not\in B\}$$
$A$ and $B$ are regular over $\Sigma$.
Is $A_1$ regular?
1
vote
1answer
45 views
Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars
I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if ...
1
vote
1answer
47 views
Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$
I started by stating that:
$|w\bar{w}| =...
1
vote
1answer
64 views
How could one prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ? Using induction
I am currently working on ways to prove this and got stuck proving it with induction.
Any tips?
How could i prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ?
1
vote
3answers
84 views
Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular
I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your ...
