Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
1answer
15 views
What is the minimun type of logical system that allows to determine if formalized sentence is well-wormed formula or not boolean type?
The formula, in the old way of using it, can contain symbols in order and a mixture that does not meet the criteria of correctness. Also, a sentence written in a natural language could be in such a ...
7
votes
1answer
227 views
Is unary language with polynomial power context sensitive?
I suppose that $\Sigma = \{a\}$.
Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.
It ...
16
votes
2answers
929 views
Algorithm to test whether a language is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
3answers
74 views
Define a finite automaton accepting the language below [duplicate]
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.
About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
1
vote
0answers
31 views
Characterization of NFA whose equivalent (minimal) DFA has exponential number of states
(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
2
votes
1answer
29 views
Finding an unambiguous grammar of a language provided by a CFG
I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.
In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
6
votes
3answers
87 views
What is language density used for?
If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as :
$$ p_L(n) = | L \cap \Sigma^n | $$
I am wondering why it’s useful to study this function ...
0
votes
1answer
59 views
Find a CFG for $\{a^ib^jc^k \mid i,j,k\ge0 , \text{if } j=1 \text{ then } i=k\}$
I've tried but I can't figure out any solution. Is there any hint for me to solve the question?
11
votes
4answers
2k views
Star free language vs. regular language
I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example?
(from wikipdia) Lawson defines star-free ...
-2
votes
0answers
36 views
Give a regular expression for language L [closed]
guys! I am studying formal language now. There is a question:
Give a regular expression for language L={a,bb,aa,abb,ba,bbb...}.
Can anyone give me some advice? Thanks in advance!
1
vote
1answer
29 views
Can the complement of a context-free language be regular?
I know that the context-free language is not closed under the complement ,
and the result could be context-free language or non-context free language
but my question is :
is it possible of the ...
1
vote
1answer
57 views
context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Generate a cfg of $L_n$
For n = 1, 2, 3
Informally, x is in $L_n$ means
some palindrome of at least length n is a ...
1
vote
1answer
53 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
0answers
53 views
How to find the minimum number of states of a deterministic finite automaton accepting a given language [duplicate]
Let
$L$ be a language over $\Sigma$. And $\Sigma = \{0,1\}$ is a set of input alphabets.
$L = \{ w \mid w \in \Sigma^*, \text{ where $w$ is a string with numbers of 0s divisible by 3 and number of ...
4
votes
3answers
7k views
Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively?
While studying automata theory a typical problem that I face is of the following type:
Constructing a DFA with minimum number of states for all strings over
$\{a,b\}$ which have number of $a$’s ...
1
vote
1answer
42 views
Brzozowki's algorithm doesn't work for this corner case
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:
In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
2
votes
1answer
31 views
Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$
I've been stuck on this problem for a while. Any hints would be appreciated!
Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle ...
1
vote
1answer
262 views
Language whose intersection with a CFL is always a CFL
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular.
I haven't managed to prove this, but I'm ...
1
vote
1answer
58 views
Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.
I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. ...
1
vote
1answer
33 views
How to correctly describe this action, deleting an edge that “shortcut” some vertices
Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:
1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
0
votes
1answer
44 views
how can one counter machine accepts a^n b^n c^n?
It is mentioned in Which languages are recognized by one-counter machines?
that one counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?
-3
votes
1answer
41 views
Context Sensitive Grammar for the language $\{a^n b^n c^{2+k}\mid n \ge 1, 0 \le k\le 1\}$ [closed]
I'm studying for my final exam and come up with this exercise with no idea how to find the production rule of this grammar.
I need help. Thanks all of you! :)
0
votes
1answer
78 views
Finding two languages satisfying conditions
Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$
Prove that there are two languages $L_1, L_2$ such that
$L_1, L_2 $ are infinite.
$L_1 \cup L_2 = E_{TM}$
$...
2
votes
2answers
90 views
Can a TM recognize whether another TM recognizes a non-empty language?
Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$
Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?
My attempt:
I wanted to study ...
1
vote
0answers
22 views
Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$
I'm struggling with the following question:
Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{...
4
votes
3answers
6k views
How to determine if an automata (DFA) accepts an infinite or finite language?
Given an automata [DFA $A=(Q,Σ,δ,q_0,F)$], is there a way to determine whether it accepts an infinite or finite language?
1
vote
1answer
91 views
For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free
Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my ...
0
votes
2answers
43 views
Regularity of a language contains more 1's than 0's
The language of all bitstrings with more 1s than 0s, i.e.,
$ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular.
I know I should apply Pumping Lemma and the proof as well, what I cannot ...
-1
votes
0answers
16 views
Converting a formal language to Context free grammer [duplicate]
I am trying to convert Regular expression L={ a^m b^n | m ≥ 0, 2m ≥ n ≥m} to a context free grammer.How can i extract the grammer?
2
votes
1answer
61 views
CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}
I know the answer which is:
\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbT\ \mid \varepsilon
\end{align}
Now, $bbaaa$ is in the language. But the given CFG cannot generate it. ...
2
votes
1answer
69 views
What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??
1
vote
2answers
33 views
Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata? [duplicate]
I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?
1
vote
1answer
39 views
Finding the equivalence classes of a language
I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language
$$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$
The best way I've ...
0
votes
1answer
47 views
Confused about pumping lemma, What i'm missing? [duplicate]
When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.
let ${n=4}$, then $w=010000$...
0
votes
0answers
31 views
How to generate random strings from Context-Free Grammar in GNF
I need to generate random strings given a grammar in Greibach Normal Form.
The naive approach would be to generate a random integer n and perform ...
-1
votes
0answers
30 views
Find a context-free grammar for L={(a^n b^m)^z d^z} [duplicate]
need a CFG for the following language:
$L={(a^n b^m)^z d^z}$
$m=2n, \ \ \ n,z \\$≥0
Any ideas?...
0
votes
1answer
38 views
Context free grammar for L={ ((ab)^n)^m }
I want to write a cfg for the following language:
$ L = {((ab)^n)^m }$ $m,n >= 0$
this language produces (abababababab) where: $n=2, m=3 \\ or \\ n=3, m=2$
I have no idea what to do with it!
10
votes
2answers
705 views
Language involving irrational number is not a CFL
I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}$ ...
1
vote
1answer
53 views
Polynomial Time reducible explanation
Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct?
If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
3
votes
4answers
15k views
Designing a DFA that accepts strings such that nth character from last satisfies condition
This is a homework question, so I am only looking for hints.
I got a question in an assignment which states :
Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
2
votes
3answers
435 views
Example of a parsing/rewriting system?
I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually ...
7
votes
1answer
104 views
Proof of Brzozowski's algorithm for DFA minimization?
Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it ...
43
votes
1answer
10k views
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?
Anyway, here'...
0
votes
0answers
27 views
Show that the following languages are equal [duplicate]
I have the following exercise:
Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$.
My idea was to write the words of each of the languages in the following way,for example for the ...
9
votes
3answers
12k views
What is complement of Context-free languages?
I need to know what class of CFL is closed under i.e. what set is complement of CFL.
I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
1
vote
1answer
35 views
Pumping Lemma on Language with subtracted length
My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given
$$ L = \{ a^k b a^{m-...
2
votes
3answers
281 views
What parts of a programming language can't be defined using Regular Expressions?
I'm trying to understand how the syntax of some programming language is defined.
I know that there are some parts of the syntax of programming languages that can't be defined using regular ...
0
votes
0answers
28 views
How to check if a string is accepted by a context-sensitive grammar?
Is there an algorithm to determine membership in context-sensitive grammars?
1
vote
2answers
31 views
Program to check whether a string is accepted by an unrestricted grammar
How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?
3
votes
1answer
45 views
Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.
The professor hasn't given the correction.
I have seen similar questions but the condition ...
