Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

1
vote
0answers
18 views

Are deterministic context-free languages closed under reversal of languages? [duplicate]

It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that ...
3
votes
1answer
75 views

Difference between substitution, morphism, and homomorphism

In closure properties, I got confused between substitution and morphism. 1) According to wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a ...
-1
votes
1answer
49 views

How to find the Context-free grammars for this language [duplicate]

give a context-free grammar describing the language L={w∈{a,b}∗∣w is of the form xby, where |x|>|y|}. I had one solution like this ...
0
votes
0answers
15 views

CFG for language [duplicate]

I'm trying to create CFG for a language. The language is following: {w | {a,b}* | w should have one more a than there are b: s } I built following grammar: S -> aB | aSb | bSa | abS | baS | Sab | ...
-1
votes
2answers
44 views

Infinite sequence of regular languages over fixed finite alphabet

Construct an infinite sequence of regular languages $L_1, L_2 , \ldots$, over the same fixed finite alphabet, such that for every $i ≥ 1$, $L_i ⊇ L_{i+1}$ and $|L_i \setminus L_{i+1} | = ∞$.
4
votes
1answer
110 views

Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...
0
votes
1answer
41 views

Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular [duplicate]

I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got ...
0
votes
2answers
67 views

How to prove that these two languages are regular, or not regular? [duplicate]

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
1
vote
2answers
92 views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
0
votes
0answers
36 views

A context free grammar for the language of even-length non-palindromes [duplicate]

I am trying to find a context free grammar for the language $L = \{xy \mid |x|=|y| \text{ and } x≠y^R\}$ where $y^R$ is the reverse of string y and $x, y\in \{a,b\}^*$ . Here is a possible ...
2
votes
2answers
43 views

How can I see which language type will result from the union or intersection of different language types?

I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language. Is there a way or rule to decide this for all language types?
4
votes
1answer
106 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
3
votes
1answer
109 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
-1
votes
1answer
32 views

Kleene star property: proving $(A^+)^* = A^*$ [duplicate]

I should prove that $(A^+)^* = A^*$ in a very formal way, any hints?
-5
votes
2answers
65 views

Does complement distribute over concatenation?

Prove or disprove $\exists L_{1},L_{2}\subseteq\Sigma^{*}:\quad L_{1}\ne L_{2}\wedge\overline{L_{1}\cdot L_{2}}=\overline{L_{1}}\cdot\overline{L_{2}} $ Where $\cdot$ means concatenation, and over ...
5
votes
2answers
709 views

Can a Language be determined by its kleene closure?

Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from ...
3
votes
1answer
101 views

Prove that regular expression is unambiguous

I've got following definition: Function $f$ is a valid mapping of word $w$ to regular expression $R$, if any of following conditions is true: $R = w$ and $f$ is the identity or $R = \epsilon$ and ...
0
votes
0answers
52 views

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
-2
votes
1answer
55 views

How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$? [duplicate]

I have a language $\{a^m b a^n | m+n \equiv 1 mod 3\}$ $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ... $m+n$ is the number of all $a$'s in the word How can I build a DFA for this language?
0
votes
2answers
42 views
1
vote
1answer
62 views

How can I quickly guess if L is context-free or det. context-free?

I have a language, for example $\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$ $\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$ How can I see at a glance whether the language is deterministic ...
0
votes
0answers
84 views

How to convert the following grammar to LL(1)?

The following grammar is given: \begin{align*} M &\rightarrow d M d \\ M &\rightarrow e M e \\ M &\rightarrow f M f \\ M &\rightarrow \varepsilon \end{align*} I've checked it with ...
2
votes
1answer
19 views

Complexity of self-reducible set

I am trying to solve the following problem: A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where ...
-2
votes
1answer
74 views

Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)? Moreover, can an $O(n^2g(n))$ ...
0
votes
0answers
16 views

Pumping Lemma for CFG - How to do it? [duplicate]

I'm literally so confused on how to even start this problem of proving that the given language is not Context Free. L = {a^i b^j c^k d^l | i = k and j = l} I ...
1
vote
2answers
63 views

Are regular languages closed against an intersection that keeps words with the same number of ones?

How can we show that the class of regular languages is closed under the following operation? Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$. The operation is: $$\{x \in L_1 \mid \text{ for ...
2
votes
1answer
72 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
0
votes
0answers
46 views

Why is this language is not context-free? [duplicate]

Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
0
votes
2answers
82 views

Intersection of a language with a regular language imply context free

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is ...
0
votes
2answers
75 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= ...
1
vote
1answer
77 views

Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]

This is a question from a text book that's giving me some trouble. The question is: Determine whether or not this language is regular. Justify your answer. $$L = \{ww : w \in \{a,b\}^* \}$$ I ...
-1
votes
1answer
57 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA ...
0
votes
1answer
36 views

True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

Question: Is the following statement true or false? If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable I thought that since every language is automatically of type 0, it follows that $A ...
4
votes
1answer
65 views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
0
votes
1answer
44 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
0
votes
1answer
38 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
3
votes
1answer
156 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0:xyiz\in L$ I don't understand why the length of ...
2
votes
0answers
47 views

Removing hidden ambiguity in grammar using left factoring

I am trying to reduce the grammar to LL(1) for a hypothetical language we created. I have removed most of the left factoring issues in the grammar, using the general rule of introducing new ...
1
vote
1answer
37 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
0
votes
1answer
81 views

If L1 ∪ L2 and L1 are regular, is L2 also regular?

This is a problem in a theory of computation book that's stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I ...
0
votes
0answers
24 views

How these languages are context free and regular [duplicate]

I found these statements in my textbook without proof. If L is a Context Free Language over a one symbol alphabet then L is regular. Is there no context free language on one symbol ...
0
votes
1answer
64 views

Pumping Lemma confusion

I have the following language... $$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$ Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is ...
2
votes
1answer
98 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
2
votes
1answer
146 views

Language consisting of all Turing machine encodings [closed]

$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ } What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL? I would say $A$ is decidable since we can write an algorithm to check ...
1
vote
1answer
36 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1
vote
1answer
87 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
2
votes
0answers
39 views

Tightest upper bound on length of distinguishing string in Hopcroft's algorithm

Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable. What is the tightest possible upper bound (with proof) on the ...
0
votes
0answers
28 views

What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
0answers
17 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
0
votes
1answer
98 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...