Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
0answers
7 views
What is the minimun type of logical system that allows to determine if formalized sentence is well-wormed formula or not boolean type?
This question has two parts. On the other hand I'd like to get a clarification what kind of theoretical and logical framework is required to implement a system that has propositional and predicate ...
0
votes
3answers
73 views
Define a finite automaton accepting the language below
$\{ 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 ...
-2
votes
0answers
35 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 ...
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 ...
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
261 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 ...
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 ...
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! :)
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
21 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}{...
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}$
$...
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 ...
-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?
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 ...
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. ...
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 ?
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
704 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 ...
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 ...
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 ...
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?
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 ...
3
votes
0answers
24 views
Automaton without stack for visibly pushdown languages
This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...
1
vote
0answers
22 views
(Non) Context Free Language…? [duplicate]
I hope you could help me as you have done before (thanks again)
In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL.
In my opinion this ...
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
0answers
50 views
Grammar for context free language
I want to give a grammar for the following language:
$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written ...
0
votes
1answer
38 views
Is this language L context-free?
The language
$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$
where $x ^ r$ denotes the backward written word x, is context-free.
Can someone ...
0
votes
0answers
28 views
Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free
I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language.
Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt.
Proof. Suppose by ...
2
votes
2answers
48 views
Is there a way a proving a language regular/non-regular that works for every possible language?
In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-...
1
vote
1answer
56 views
Does a Context-free language have a grammar that has either 3 or 0 nonterminals on the right hand side?
Is the following true or false? Why?
Let L be a context-free language with $\epsilon\notin$ L. Then there is $\epsilon$-free grammar $G=(V,\Sigma, P,S )$ with $L (G) = L$, so all production rules are ...
1
vote
1answer
45 views
Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?
I've been asked to write a DFA for:
$\{xy\mid x, y \in \Sigma^*\text{ and }x\text{ contains more }a\text{’s than }y\}$ where $\Sigma=\{a,b\}$.
I don't believe this is possible. Can anyone confirm if ...
2
votes
2answers
48 views
Union of a regular and a non-regular language
Let's say we have $L_1$ which is a regular language and $L_2$ which is not.
I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language.
Does that implicitly mean that ...
-1
votes
1answer
41 views
Find the language from a context free grammar
I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out.
$$G= (\{S,A,B,C,D,E,Z\},(0,...
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 ...
1
vote
1answer
377 views
Is a particular string regular (e.g is '010') regular?
If the alphabet is $\{0,1\}$, then is the string '010' regular?
I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to ...
0
votes
0answers
38 views
How can I find a language from a given PDA
I have the following PDA:
And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{...
1
vote
1answer
46 views
Let u and v be two strings. What about the reverse order of their concatenaited string?
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?
Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.
1
vote
1answer
28 views
Converting CFG from GNF to CNF
I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is ...
