Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

0
votes
1answer
19 views

Proving that a language having a particular CFG grammar is equivalent to a particular L

I think we need to prove that L(G) is a subset of L and then we need to prove that L is a subset of L(G). For the first part, I think we need to say for any w in L(G) we have an even number of as ...
1
vote
1answer
22 views

Particular Problem for Context Free Grammars

Consider the context-free-grammar $G$ defined by productions: $$ S \rightarrow aS\,|\,Sb\,|\,a\,| b $$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
2
votes
1answer
20 views

Equivalence of two regular expression

I have a quick question to ask. So I am trying to come up with a regular epxression which represent a language over {a,b} that contains at least one 'b' in it. I came up with this: $$(a| b)^*b(a| ...
0
votes
1answer
26 views

Create a general NFA for $M_n$

I need to create a general NFA $M_n$ where $n \in \mathbb{N_0}$ with the following language defined: $$L(M_n) = \left\{ w \in \{0,1\}^* \big | x1y \textit{ for } x \in \{0,1\}^* \textit{ and } y \in ...
0
votes
1answer
30 views

find a regular expression and FA that each define L1 ∩ L2

from the following pairs I am trying to find a regular expression and FA that each define ...
5
votes
3answers
375 views

Finite Automaton that accepts only the words baa,ab, abb and no other strings longer or shorter

I am trying to understand the answer here for FA that accepts only the words baa, ab, abb and ...
0
votes
1answer
20 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
22 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
2
votes
0answers
49 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
3
votes
3answers
62 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
2
votes
1answer
32 views

Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
0
votes
1answer
18 views

Pumping lemma clarifications

http://www.cs.oberlin.edu/~asharp/cs383/handouts/pumping.pdf I came across this and realized that what some people told me was completely wrong. We get to choose xyz, but the demon choose uvw and uvw ...
1
vote
1answer
45 views

Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
0
votes
1answer
39 views

How do we choose a good string for the pumping lemma?

we have a Language $$\mathscr L: \{a^mb^n: m \ne n\}$$ we need to choose a good string $w$. apparently $w = a^{n+1}m^{n}$ is not a good string. can someone explain why? I also found this and I ...
0
votes
2answers
72 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
1
vote
0answers
18 views

Can the NFA constructs be minimized?

When converting a regular expression to a NFA you need to use certain constructs. My question is can these constructs be minimized? We have one with 4 states, I want to use the one with 2 states ...
1
vote
2answers
44 views

How do we prove that a particular DFA is minimal?

I guess we need to prove that there is no redundant state, so can we use state elimination and prove that the regular language is minimal? We could prove that the regular language is minimal by ...
-1
votes
1answer
23 views

transition graph that accepts only Λ and language a*

I am trying to have a transition graph that accepts only Λ and also one that accepts language a* ...is this ok ??? transition graph that accepts only Λ transition graph that accepts language a*
0
votes
1answer
28 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
0
votes
1answer
27 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
1
vote
1answer
22 views

Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
0
votes
1answer
61 views

Context free grammar to pushdown automata…

<expr> −→ <term> | <expr> + <term> <term> −→ <factor> | <term> × <factor> <factor> −→ (<expr>) | b ...
0
votes
2answers
52 views

Turing machine true/false questions

There is a non-regular language that is recognized by a Turing Machine. I believe the answer to this is true, because Turing machines can "count" computations and ...
1
vote
3answers
71 views

CFG for language l

please solve this question.thanks Consider the language L expressed by (a+b)*a defined over Σ = {a, b}. Draw FA and construct the CFG corresponding to the language L.
0
votes
2answers
101 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
0
votes
2answers
42 views

Proof by pumping lemma

Let's say that we have to prove that $L = \{ww^Rv |w,v\in \Sigma^*\}$ is irregular. I would take a string such that $w = baba^m$ and $w^R=a^mbab$ and $v = a$ and then I would pump divide $w$ into ...
1
vote
1answer
22 views

Showing that all regular languages are closed under reversal

I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be ...
4
votes
1answer
55 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, ...
2
votes
1answer
33 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
4
votes
2answers
98 views

Have action/predicate systems (or similar) been considered in the literature?

Question. Has the following concept, or anything similar, been considered in the literature? Definition. An action/predicate system consists of sets $A$ (the actions) and $X$ (the predicates) such ...
0
votes
1answer
23 views

If the language is context free?

i believe intuitively the following language is CF. But there is a book (without more description) that states the language is not CF. If I'm in a wrong way? $L=\{W_1cW_2 | W_1,W_2 \in (a+b)^* W_1 ...
1
vote
2answers
59 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
0
votes
2answers
63 views

Combining two DFAs into an NFA to recognize concatenation

Suppose we have two separate DFAs that each recognize their own language. What is the most efficient way to combine these two DFAs into one NFA that recognizes the concatenation of both languages?
1
vote
1answer
31 views

How to construct a grammar G such that L(G)={x^ny^mx^my^n/m,n>1}?

construct a grammar $G$ such that $L(G)=\{x^ny^mx^my^n/m,n>1\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these kinds of problem?
0
votes
2answers
207 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
1
vote
2answers
43 views

Why is a 3-PDA no more powerful than a 2-PDA?

A k-PDA is a pushdown automata with k stacks. My textbook on Computation Theory has an exercise that asks to prove that 3-PDA is no more powerful than a 2-PDA. Now consider the language that I made ...
3
votes
1answer
40 views

Proof of a Known Claim About Languages

I would like to know how to prove that there is no non-trivial language $L$ that satisfies the following condition: $${\large \left(\overline{L}\right)^* = \overline{L^*}}$$ "Non-trivial" is ...
0
votes
1answer
19 views

Reversed Language of a Non Regular Language

Is the following saying true or false? In any case why? Thanks!
2
votes
1answer
38 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
0
votes
2answers
32 views

What method should you follow to show what a DFA does?

I'm specifically looking for help analyzing the following DFA. What steps would one follow to show what language this particular DFA accepts? To me it seems quite random, and I can't figure out a ...
1
vote
2answers
45 views

Reduction between two languages and a common one

My question is as following : Let $A$ and $B$ be some languages, there exist a language $C$ such that $A\le C$ and $B\le C$, where "$\le$" means "reducible to", so $A\le C$ means there is a mapping ...
0
votes
2answers
30 views

Determining a language with a Turing Machine

How can I build a Turing Machine that determines the following language? $$L_{E - DFA} = \{\langle A \rangle | \text{$A$ is a $DFA$ and $L(A) = \varnothing$}\}$$ Thanks alot
0
votes
1answer
75 views

Why isn't this a sufficient proof?

So basically, we have a question that asks us to prove that given a particular Deterministic finite automaton (DFA), there is a symbol for which we can get to a state $q$ from a state $p$ given a ...
0
votes
3answers
20 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
1
vote
3answers
61 views

NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $ (ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
1
vote
1answer
49 views

Is the PDA I drew correct?

Could you tell me if the language $L=\{a^{m}b^{n}:m \neq n,m>0,n>0 \} $ is accepted by the following pushdown automaton, where the alphabet of the stack is $\{a,z\}$ and $z$ is the initial ...
1
vote
0answers
46 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
2
votes
1answer
51 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
1answer
36 views

Languages that are not comparable in $R$

I want to know if there are $2$ languages $A,B\in{R}$ such that there's no reduction between them. Namely, $2$ languages $A$ and $B$ $\in$ $R$ such that $A\not\le B$ and $B\not\le A$ Thanks a lot!
0
votes
2answers
48 views

Determining whether a language belongs to R or RE (Turing Machines)

Does the language L belong to R, RE or neither? In each case, why? Thanks a lot!