Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

1
vote
1answer
34 views

Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?

I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be ...
0
votes
1answer
35 views

Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA: I prepared below tables and finally the NFA: NFA However I feel I am wrong here, since original NFA does not have any transitions defined for state C ...
5
votes
1answer
87 views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, ...
-1
votes
1answer
57 views

Prove Language Is Union of Fninitely Many Arithmetic Progressions [closed]

So, you see in the image the question and its answer (proof below the black line). I get the entire proof until the last formula. It basically says that if length of a string is larger than number of ...
1
vote
1answer
40 views

Converting a NFA to its equivalent regular expression

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions. I have the following NFA: I'm using the state ...
0
votes
1answer
38 views

algoritm to convert a monoid into an automaton [closed]

In literature, is there an algoritm to convert a monoid into an atomaton? I am looking for references/applications.
0
votes
2answers
67 views

Identifying and describing the language accepted by a Turing machine [closed]

Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?
6
votes
4answers
264 views

Relationship between formal system and formal languages

In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems. ...
0
votes
2answers
80 views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
2
votes
1answer
25 views

Undecidable definition of pure function?

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
-1
votes
1answer
71 views

Infinite u decidable languages [closed]

I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the ...
2
votes
1answer
38 views

prove that a language is context free given a regular language

R is a regular language over $\Sigma=\{0,1\}$ $Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$ I need to prove that Sub(R) is context free. I know that the quotient of a context free language with a ...
0
votes
2answers
74 views

Find a pushdown automaton for $ \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$

I was told to built a PDA that recognizes the following language: $$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$ My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
1
vote
1answer
31 views

How to create this pushdown transducer? (formal languages and automata)

Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how ...
1
vote
1answer
31 views

Rational subsets of a monoid

In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the ...
3
votes
1answer
39 views

Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular? My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number ...
0
votes
2answers
73 views

Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular [closed]

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$ I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping ...
1
vote
1answer
62 views

Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need to define a CFG for this language. ...
2
votes
1answer
227 views

Can a recursive language be uncountable?

Does there exist a recursive language $L$ whose cardinality is uncountable? I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to ...
2
votes
2answers
128 views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
2
votes
2answers
150 views

Automatic translation between formal languages

There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar. Would it be possible to make a ...
0
votes
1answer
50 views

Proving that non-regular languages are closed under concatenation

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?
5
votes
2answers
32 views

Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input ...
0
votes
1answer
47 views

Confusing example of a language which may be Context-free or not context-free

Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n ...
2
votes
2answers
42 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.
5
votes
0answers
55 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
1
vote
2answers
78 views

Prove if given language is regular or not

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$ To Prove: If given language is regular or not. I know that it is not a regular language but I am not able to come up with the string which I can ...
0
votes
1answer
26 views

If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

I am discussing with a friend the following question: If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable? I believe it is. My point ...
3
votes
1answer
55 views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
0
votes
0answers
43 views

The pumping lemma for the context free languages [duplicate]

I am trying to use the pumping lemma to show this is not a context free language $$ L = \{a^n b^{2n} a^n\mid n\ge 0\} $$ My idea is fist assume it is a CFG language and let $n$ be the pumping lemma ...
0
votes
2answers
52 views

Transforming NFA into DFA

In the examples I was given I have the following NFA diagram: Then it gives the conversion process Could someone explain to me the process of obtaining the second column: {1,2,4} = a{1, 2, 3, 4}, ...
2
votes
1answer
104 views

show that language $L'$ is regular (given $L$ regular)

I am working on the following question: $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular. Firstly I show my idea. When you accept it I will try to ...
1
vote
0answers
60 views

How to draw a clearly arranged DFA of a language with modulo rules?

I know how to draw a DFA, but I have problems with this specific one: ${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$ This language is regular and there has to exist a ...
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
98 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
56 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
45 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
112 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
42 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
71 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
94 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
45 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
108 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
112 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
33 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
711 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
108 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 ...