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

learn more… | top users | synonyms

0
votes
1answer
36 views

Writing a Context Free Grammar for a language with multiple strings in the language

I have an interest in computing and want to learn more about the actual theory behind it. Context Free Grammar plays a part and I am quite fascinated by it all. However, I came with a language that ...
0
votes
2answers
42 views

What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
1
vote
1answer
36 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
1
vote
1answer
29 views

proving that if a FFA accepts L=> L is a regular language

Ok, so after wasted time for nothing on this question that I asked yesterday: proving that a regular language can be accepted by a fast finite automaton Now comes the more interesting prove: ...
0
votes
1answer
45 views

proving that a regular language can be accepted by a fast finite automaton

Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of ...
4
votes
2answers
59 views

proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same length,...
0
votes
1answer
16 views

If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
0
votes
1answer
39 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...
1
vote
1answer
30 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
0
votes
0answers
43 views

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

(A) L is Regular (b) L is context free but not necessarily Regular (c) L is recursive but not necessarily Regular (d) L is recursively enumerable but not necessarily Recursive I could only conclude ...
1
vote
1answer
226 views

Automata | Prove that if $L$ is regular than $half(L)$ is regular too

I've see couple of approaches to this kind of questions yet I have no clue how to approach this one. Let L be regular language, and let half(L) be: $half(L) = \{u | uv \in L\ s.t. |u|=|v|\}$ Prove ...
0
votes
1answer
22 views

Show that the problem of deciding whether a Turing machine prints something is undecidable

I am unable to get the logic for showing that the problem of whether a Turing machine prints something is undecidable by showing that the halting problem reduces to it. Please guide me with this.
0
votes
2answers
27 views

difference between A* and 2^A*

let A be any input alphabet then what is the difference between A* (kleen closure of A) and 2^A* ?
1
vote
1answer
121 views

If a language is context free ,then why is the complement of the language recursively enumerable?

If a language is CFL , then it is clearly recursive and if it is recursive then it is obviously recursively enumerable but then recursively enumerable languages are not closed under complement so how ...
0
votes
0answers
149 views

Construct an NPDA for the following language: L = {a^nb^m | n>= 0, n!= m}

How we've learned is to first construct a CFG, and then use that to construct the npda. Our end goal is a transition graph. The language is $L = ${${a^nb^m | n>= 0, n!=m}$} We can think of ...
2
votes
1answer
115 views

what are the practical uses of “game of life” or “langton's Ant”

A few questions: Besides looking really cool, what are the practical uses of "game of life" or "langton's Ant"? I understand how agent-based modeling itself is a potentially useful methodoly, not ...
1
vote
0answers
43 views

why is automaton with a queue is more powerful than an automaton with a stack?

what is the logic behind this statement that with the use of queue the automaton becomes more powerful , is it that in a queue , we may do operations from both the ends as compared to a stack so it is ...
2
votes
0answers
95 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. Shouldn'...
0
votes
0answers
16 views

Question on Regular Language

L={a^($2^n$),n>1} $U$ {$a^m$,m>1} Is L a regular? My approach is-- union of a non regular and regular language may be regular or may be not regular. The left side of union is not regular so the ...
0
votes
0answers
18 views

what is the minimum no of DFA states required to recognise below language?

$L=\{a^nk , k>0 \text{ and } n \text{ is an integer constant} \}$ In this question which constant should be changed , n or k while considering the DFA since then it can be either $n+1$ or $k+1$ ?
1
vote
2answers
51 views

Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language $$A = \{w \mid \text{ w has even length ...
0
votes
1answer
35 views

Understanding the proof that uses Pumping Lemma that the language $C =\{w \mid w$ has an equal number of $0$'s and $1$'s$\}$ is not regular

I have just started reading about the Pumping Lemma, and I have some difficulties understanding the proofs of non-regularity of languages. For example, in the book I am reading there's a proof for ...
0
votes
2answers
24 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
1
vote
0answers
47 views

Evaluating $b^*a^*\cap a^*b^*$ to a minimal regular expression

Evaluate to a minimal expression: $b^*a^*\cap a^*b^*$ To me, the only elements to both sets are the empty string, strings containing only $a$, and strings containing only $b$, so isn't the answer ...
1
vote
0answers
109 views

The set of all strings with twice as many 0's as 1's

I have to create a PDA that accepts strings with twice as many 0's as 1's. So far I have decided to create one which accepts via empty state: (q0, 0, Z0) - (q1, 0) (q0, 1, Z0) - (q1, 11) (q1, 1, 1)...
1
vote
1answer
38 views

Prove the infinite union is not regular

Prove $\bigcup _{i=1}^\infty A_i$ is not regular. We know $A_i$ is regular, but how can prove the infinite union is not regular. I think a counter example would work, but I can't think of any. ...
2
votes
1answer
75 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
1
vote
1answer
27 views

Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
0
votes
1answer
184 views

How we decide for a given context free grammar generate an infinite number of strings?

Consider the following decision problems: (P1) Does a given finite state machine accept a given string? (P2) Does a given context free grammar generate an infinite number of strings? Which of the ...
1
vote
0answers
27 views

Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
0
votes
1answer
53 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
1
vote
0answers
29 views

Are languages that contain the empty string Turing-Decidable?

Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable? I am very confused at this problem because from my understanding the ...
1
vote
1answer
784 views

Minimum Pumping Length

What is the minimum pumping length of (01)* The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be 0. ...
1
vote
0answers
27 views

Intersection automaton of two automata

I need to build the intersection automaton of these two automata My attempt: My attempt is correct?
0
votes
0answers
20 views

Are languages made by splitting regular lanaguage regular?

Let's have language $L$: $L = \{u·v, u ∈ L_1, v \in L_2\}$ Lanaguage $L$ consists of words from $L_1·L_2$. We know that $L$ is regular language. In other words languages $L_1$ and $L_2$ are made by ...
0
votes
1answer
15 views

Are these two grammars similar?

Language is L = {a^nb^m | n.m >=1} Grammar 1 : S->AB B -> bB|b A-> aA|a Grammar 2 : ...
1
vote
1answer
17 views

Regular language or not : XAB where X,A belongs to (0,1)+

I am working on a problem a) L1={XAB | X,A belongs to (0,1)^+ and B is Reverse of A} i have to check whether this language is regular or not. I am trying to do ...
0
votes
1answer
39 views

Regular expression for language containing all strings that start and end with different symbols

ques - Regular expression for language containing all strings that start and end with different symbols i just went through some examples where the RE for above question is ...
0
votes
1answer
39 views

Does an NFA with a non-empty anf non-full language recognize a string with of length at most its number of states? [closed]

Let $N = (Q,\Sigma,\Delta,s,F)$ be an NFA (nondeterministic finite automaton) such that $L(N)\ne \emptyset$ and $L(N)\ne \Sigma^*$. Prove or disprove the following. $$\exists x \in L(N): \lvert x ...
0
votes
1answer
60 views

Show there is a string that's length is less than or equal to the number of states in an NFA

I'm trying to prove that this is true but cannot find a good way to show this proof. The question is below: Let $T$ be an NFA such that the language defined by $T$ is neither empty nor $\Sigma^*$. ...
0
votes
2answers
318 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
0answers
28 views

Constructing a push down automaton

I'm having trouble constructing a PDA for the following language: $$L=\{x\#y\#z\mid x,y,z\in\{a,b\}^+\text{ with }x\approx y\text{ or }x\approx z\text{ or }y\approx z\}$$ Define $x\approx y$ as ...
1
vote
3answers
47 views

Trying to convert DFA to regular expression

I'm trying to write a regular expression from this DFA but I'm having some trouble. I can tell you what I've done so far: I started by adding a new beginning state and a new final state because ...
0
votes
2answers
26 views

Creating DFA to prove closure properties

I am given a language $L \subseteq \Sigma^*$ and symbol $a \in \Sigma$. Let $a/L= \{ w \in \Sigma^*~|~ wa \in L \}$ ex. String that end in $a$ but with that last $a$ removed. I am trying to prove that ...
2
votes
3answers
105 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...
0
votes
1answer
41 views

Prove if a language is infinite

Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove: The languge T(M) is infinite iff contains a string with lenght t, where n ≤ t < 2n. Ok, it's intuitive for me, I can understand to get a string ...
0
votes
1answer
24 views

Find languages L1 and L2, neither of which contains the other, such that (L1* ∪ L2*) = (L1 ∪ L2)*. [closed]

I'm trying solve this question in several ways, but only textbook has not helped me alot.
0
votes
1answer
44 views

Is $L = \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ context free language?

I have doubt , regarding this question Is this language is context free ? $L= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ IMO : push all $a$'s , match with $a$ and pop $b$'s ,(now stack ...
1
vote
0answers
38 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
0
votes
0answers
172 views

Construct DFA from context-free grammar

What is simplest and shortest way to build minimal DFA from context-free grammar (equivalent to regular grammar)? For example, the grammar: A ::= aB B ::= {b} ...